<?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 Valeriy Krygin on Medium]]></title>
        <description><![CDATA[Stories by Valeriy Krygin on Medium]]></description>
        <link>https://medium.com/@valeriy.krygin?source=rss-f7c029f045f0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*9WtNPDIDgsztGfJe</url>
            <title>Stories by Valeriy Krygin on Medium</title>
            <link>https://medium.com/@valeriy.krygin?source=rss-f7c029f045f0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 11:22:34 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@valeriy.krygin/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[EM Algorithm as I Know It]]></title>
            <link>https://medium.com/@valeriy.krygin/em-algorithm-as-i-know-it-f0a39a10e704?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/f0a39a10e704</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[clustering-algorithm]]></category>
            <category><![CDATA[unsupervised-learning]]></category>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[statistics]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Sun, 01 Nov 2026 11:59:36 GMT</pubDate>
            <atom:updated>2026-11-01T12:35:53.848Z</atom:updated>
            <content:encoded><![CDATA[<h4>Dedicated to Prof. Dr Michail Ivanovich Schlesinger​</h4><p><a href="https://image.irtc.org.ua/michail-i-schlesinger/">Prof. Dr Schlesinger</a> invented the famous unsupervised learning algorithm —the EM algorithm. More precisely, the first complete description of a discrete case of the EM algorithm known to me was published as the article &quot;<a href="https://doi.org/10.1007/BF01073742">The interaction of learning and self-organization in pattern recognition</a>&quot; in 1968 — almost ten years before &quot;<a href="https://doi.org/10.1111%2Fj.2517-6161.1977.tb01600.x">Maximum Likelihood from Incomplete Data via the EM Algorithm</a>&quot; by Arthur Dempster, Nan Laird, and Donald Rubin. Michail Schlesinger did not name the algorithm “Expectation-Maximisation” — he used the term “self-organization” instead.</p><p>During his lectures, Prof. Dr Schlesinger was saying, &quot;You should know this algorithm as if you have invented it!&quot; While I did not reach that level of understanding of the applied part of the EM algorithm, I internalised the proof in slightly different terms than he presented in his original paper or in his lectures, where I had the honour of being a student for years (and eventually becoming a lecturer myself).</p><p>The entire algorithm inference and monotonicity proof is not too long and can be written as a single chain of equalities with one inequality within (and a couple of redefinitions for shortness):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*__8yfkrwb8F4MOu93WNVmw.png" /><figcaption>Formula by the Author: <a href="https://math.embed.fun/57sAZUdNz2FbCLxH4uHjKv">https://math.embed.fun/57sAZUdNz2FbCLxH4uHjKv</a></figcaption></figure><p>You may start by jumping straight to <a href="#eaf4">The EM Algorithm</a> because this story starts from the “reinvention” of this algorithm and proving its main quality.</p><h3>Table of Contents</h3><ul><li><a href="#1e4e">Expanding Log-Likelihood</a></li><li><a href="#7173">Improving The Log-Likelihood</a><br>- <a href="#6667">Prior Probabilities</a><br>- <a href="#32e4">Conditional Probabilities</a><br>- <a href="#90a7">Posterior Probabilities</a><br>- <a href="#d892">Monotonicity of The EM Algorithm</a></li><li><a href="#ff40">Correctness of The EM Algorithm</a></li><li><a href="#eaf4">The EM Algorithm</a><br>- <a href="#8a2d">Input</a><br>- <a href="#3587">Initialisation</a><br>- <a href="#24ac">Expectation (The E-Step)</a><br>- <a href="#d9b8">Maximisation (The M-Step)</a><br>- <a href="#2b4f">Result</a></li><li><a href="#8a03">Conclusions and Further Directions</a></li></ul><h3>Expanding Log-Likelihood</h3><p>Our aim is, given a finite non-empty random sample of observations, to cluster it without providing any information about the desired assignments for any items of the sample.</p><p>That is why the algorithm inference starts with a random sample — a tuple of mutually independent random variables. As we know, the probability of a tuple of independent random variables is a product of their probabilities. Thus, the logarithm is a sum of logarithms of the probabilities, also known as a log-likelihood. The superscript index <em>t</em> means the step number because we are exploring an iterative algorithm:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2F3E5dLsZiRibBW6MtfVneB&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F3E5dLsZiRibBW6MtfVneB" width="661" height="172" frameborder="0" scrolling="no"><a href="https://medium.com/media/3e0991cc82bc4ea0220f185f7d550f1e/href">https://medium.com/media/3e0991cc82bc4ea0220f185f7d550f1e/href</a></iframe><p>What is next? We need an equivalent representation of the observation probability that preserves the equalities but moves us forward. For this purpose, we introduce <em>K</em> — a set of clusters <em>k</em> to group observations <em>x</em> into. We also assume each cluster has an unknown prior probability <em>p(k)</em> and that observations and clusters are statistically connected by an unknown joint probability <em>p(x, k)</em>. Let us apply the conditional probability formula in reverse to expand <em>pᵗ(x)</em>:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FjYVwFWHckZz3ZrS2dN9aRy&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjYVwFWHckZz3ZrS2dN9aRy" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/562d55a1fc5588d13644834bc34adb58/href">https://medium.com/media/562d55a1fc5588d13644834bc34adb58/href</a></iframe><p>Then, for an arbitrary <em>k</em> such that <em>pᵗ(k | x)</em> and <em>pᵗ(k)</em> are non-zero, we have</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FnRXa7e9pcM8V1xcR27sebQ&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FnRXa7e9pcM8V1xcR27sebQ" width="657" height="185" frameborder="0" scrolling="no"><a href="https://medium.com/media/034a62a0db17da9dde58b18c59986e6e/href">https://medium.com/media/034a62a0db17da9dde58b18c59986e6e/href</a></iframe><p>We have a problem: if the posterior probability in the denominator is zero, the entire sum is undefined (division by zero). For each <em>x</em>, we need to use only such <em>k</em> that avoids this uncanny situation. I will introduce predicates, <em>π</em>, that say whether we can use the specific term or whether it yields an incorrect expression, and define that, if <em>π</em> is zero, the logarithm is ignored:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FuFpQQCMSxpYxWvwAEFghDW&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FuFpQQCMSxpYxWvwAEFghDW" width="447" height="282" frameborder="0" scrolling="no"><a href="https://medium.com/media/848a570c4dd7c914efad5beec07a6f7c/href">https://medium.com/media/848a570c4dd7c914efad5beec07a6f7c/href</a></iframe><p>How do we unambiguously choose which predicate is non-zero? Before answering this question, I will <a href="https://en.wikipedia.org/wiki/Linear_programming_relaxation">relax</a> the conditions and use &quot;fuzzy&quot; predicates — weights:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FoFpikGvX8dHKz5P45bQjSS&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FoFpikGvX8dHKz5P45bQjSS" width="447" height="282" frameborder="0" scrolling="no"><a href="https://medium.com/media/96fdb4bc90b7125e3cdce906b669362f/href">https://medium.com/media/96fdb4bc90b7125e3cdce906b669362f/href</a></iframe><p>Now, let us think of a non-negative quantity that depends on <em>k</em> and <em>x</em>, sums to <em>1</em> over all elements of <em>K</em>, and becomes <em>0</em> whenever the joint probability of <em>x</em> and <em>k</em> is zero. It is the posterior probability!</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2F4HRUX7ymCbsbbf4CAueePc&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F4HRUX7ymCbsbbf4CAueePc" width="499" height="305" frameborder="0" scrolling="no"><a href="https://medium.com/media/7bedd7d836f89533a034ac7e9261d341/href">https://medium.com/media/7bedd7d836f89533a034ac7e9261d341/href</a></iframe><p>Can the numerator be zero when the posterior probability is not? No. Because the probability of any observation is non-zero (if we faced the observation <em>x</em>, it is probable, thus <em>p(x) &gt; 0</em>), and the implication is just an application of the conditional probability formula:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2Fho3VrdSdpHsWvcFjRykmSt&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fho3VrdSdpHsWvcFjRykmSt" width="864" height="96" frameborder="0" scrolling="no"><a href="https://medium.com/media/b9681dcbcfb22d436eb6611d31d6d25c/href">https://medium.com/media/b9681dcbcfb22d436eb6611d31d6d25c/href</a></iframe><p>By applying the conditional probability formula once more, we obtain the numerator, proving it is greater than zero if the posterior probability is greater than zero:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2Fp3scFZL4V3d7uSgJoq4seM&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fp3scFZL4V3d7uSgJoq4seM" width="562" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/931ed9121026961d0de28d89d657b727/href">https://medium.com/media/931ed9121026961d0de28d89d657b727/href</a></iframe><h3>Improving The Log-Likelihood</h3><p>We aim to obtain probabilities that increase the log-likelihood, which is the iteration of the EM algorithm. I will expand the logarithm to reveal that the log-likelihood contains an entropy and cross-entropies:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FjnmDV5ZotaJppHgC1p7KKG&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjnmDV5ZotaJppHgC1p7KKG" width="551" height="216" frameborder="0" scrolling="no"><a href="https://medium.com/media/01527e7a9970135781e1755dbebeee69/href">https://medium.com/media/01527e7a9970135781e1755dbebeee69/href</a></iframe><h4>Prior Probabilities</h4><p>As long as prior probabilities <em>pᵗ(k)</em> are not tied to any statistical model, we can optimise the member that contains them without significant complications. To solve the problem, we can use the <a href="https://en.wikipedia.org/wiki/Lagrange_multiplier">method of Lagrange multipliers</a>, but I will go straight to the solution:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FpC32RS2rGi6ZLxzXw8yyMM&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FpC32RS2rGi6ZLxzXw8yyMM" width="533" height="234" frameborder="0" scrolling="no"><a href="https://medium.com/media/9534f715c3b12b4b079a1d3c7606c398/href">https://medium.com/media/9534f715c3b12b4b079a1d3c7606c398/href</a></iframe><h4>Conditional Probabilities</h4><p>Optimising the first sum in the expanded log-likelihood expression is less trivial to achieve. If we used the <a href="https://en.wikipedia.org/wiki/Lagrange_multiplier">method of Lagrange multipliers</a> again, we would achieve nothing good, because by <a href="https://en.wikipedia.org/wiki/Gibbs%27_inequality">Gibbs&#39; inequality</a>, the answer would be <em>p(x | k) = p(k | x)</em>. We must pick constraints for the probabilities — a [generative] statistical model <em>P</em>, and pick such a probability from it that does not decrease the sum:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FPSAUrPcdvVmtLt32mTHyU&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FPSAUrPcdvVmtLt32mTHyU" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/5081c9ae8d8e8753d162a573f5d9d6f0/href">https://medium.com/media/5081c9ae8d8e8753d162a573f5d9d6f0/href</a></iframe><p>When possible, we want to solve the optimisation problem</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FkBNiZhzYWHHyZ4dfM8vdzr&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FkBNiZhzYWHHyZ4dfM8vdzr" width="324" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/b590291269858fb06807dfba2ed4f318/href">https://medium.com/media/b590291269858fb06807dfba2ed4f318/href</a></iframe><h4>Posterior Probabilities</h4><p>The last sum in the expanded log-likelihood expression contains logarithms of conditional probabilities that can be computed using Bayes&#39; rule from the probabilities we already altered, so we apply the rule:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FcEi5PeLH7RsBD4mmDnckD5&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FcEi5PeLH7RsBD4mmDnckD5" width="330" height="174" frameborder="0" scrolling="no"><a href="https://medium.com/media/d5781bd77ddd3616f4a4e440a6db0a9c/href">https://medium.com/media/d5781bd77ddd3616f4a4e440a6db0a9c/href</a></iframe><p>The <a href="https://en.wikipedia.org/wiki/Gibbs%27_inequality">Gibbs&#39; inequality</a> states that the information entropy of a distribution is not greater than its cross-entropy with any other distribution. The modification of posterior probabilities changed the entropy into a cross-entropy, so it is not less than the original value:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FijyC2XDQrnURLELsP4Vqs5&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FijyC2XDQrnURLELsP4Vqs5" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/7eb3148bbbb27723459f04d7add9b2d7/href">https://medium.com/media/7eb3148bbbb27723459f04d7add9b2d7/href</a></iframe><h4>Monotonicity of The EM Algorithm</h4><p>Each summand of the expanded log-likelihood did not decrease after the algorithm iteration, which means the entire expression did not decrease:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2F4Y1souEXkywJWbLpCM3Ho3&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F4Y1souEXkywJWbLpCM3Ho3" width="586" height="319" frameborder="0" scrolling="no"><a href="https://medium.com/media/98bf482b47fc9ec5f1d4025c6541496e/href">https://medium.com/media/98bf482b47fc9ec5f1d4025c6541496e/href</a></iframe><h3>Correctness of The EM Algorithm</h3><p>Using the conditional probability formulae as we did in the beginning, we fold the right-hand side of the inequality:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2Ft2F5DqtXKUoW7euBDb4y7Q&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Ft2F5DqtXKUoW7euBDb4y7Q" width="960" height="128" frameborder="0" scrolling="no"><a href="https://medium.com/media/514ba3e68f84ec2d7afe656a77198a6a/href">https://medium.com/media/514ba3e68f84ec2d7afe656a77198a6a/href</a></iframe><p>The logarithm does not depend on <em>k</em>, so it can be moved out of the inner sum using the distributivity of multiplication over addition:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FfrUXMYEnRCo7GfF26JMSaS&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FfrUXMYEnRCo7GfF26JMSaS" width="633" height="172" frameborder="0" scrolling="no"><a href="https://medium.com/media/71f5b98a1e4419fedd9a9d0909d57b8e/href">https://medium.com/media/71f5b98a1e4419fedd9a9d0909d57b8e/href</a></iframe><p>Then the inner sum equals 1, because it sums probabilities over the entire set of independent events, so we get our new log-likelihood</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FcC5hb2mbKNSV89zugefqBU&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FcC5hb2mbKNSV89zugefqBU" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/982382ea989bba5733e5e96f54f135a8/href">https://medium.com/media/982382ea989bba5733e5e96f54f135a8/href</a></iframe><p>We have what we wanted — the quantity that does not decrease after any algorithm iteration is the log-likelihood of the input sample.</p><h3>The EM Algorithm</h3><h4>Input</h4><ul><li>A sample, <em>x</em>, of observations (order and repetitions do not matter).</li><li>A finite number, <em>|K| &gt; 2</em>, of clusters.</li><li>A non-empty family, <em>P </em>∋<em> p</em>ₓ|ₖ, of generative models.</li></ul><h4>Initialisation</h4><p>I described “the next” step of the algorithm, but I never mentioned the first step. Honestly, I do not know any general good advice on initialisation, and I guess nobody does (maybe a general simple recommendation does not exist). What I can advise is: if you do not have anything better, initialise the clusters randomly.</p><p>For example, for each <em>x</em>, you can select a random <em>k</em>, and say <em>p⁰(k | x) = 1</em>, and, for all other <em>k’ ≠ k</em>, say <em>p⁰(k’ | x) = 0</em>. From here, you can compute <em>p¹(k)</em> and <em>p¹(x | k)</em>, and proceed. This may work; sometimes it may not.</p><p>Alternatively, you may sample parameters of the generative model, <em>p⁰(x | k)</em>, and the prior probabilities, <em>p⁰(k)</em>, but the exact initial values sampling method (or hand picking) depends on your problem.</p><h4>Expectation (The E-Step)</h4><p>This is the easy part of the algorithm, but computationally nasty because it involves averaging of potentially very small numbers:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FqZHhX9kDwVFUu559pzQLhh&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FqZHhX9kDwVFUu559pzQLhh" width="200" height="173" frameborder="0" scrolling="no"><a href="https://medium.com/media/8aedd3b1205c0669ea357d1221ecc5ea/href">https://medium.com/media/8aedd3b1205c0669ea357d1221ecc5ea/href</a></iframe><h4>Maximisation (The M-Step)</h4><p>In general, this is a very hard part, because maximisation problems can be very hard:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FkBNiZhzYWHHyZ4dfM8vdzr&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FkBNiZhzYWHHyZ4dfM8vdzr" width="324" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/b590291269858fb06807dfba2ed4f318/href">https://medium.com/media/b590291269858fb06807dfba2ed4f318/href</a></iframe><h4>Result</h4><p>The result is an improved (or at least not degraded) log-likelihood of the input sample:</p><iframe src="https://cdn.embedly.com/widgets/media.html?url=https%3A%2F%2Fmath.embed.fun%2FbjFHti6uHtqr26pEqH6T2&amp;type=text%2Fhtml&amp;schema=embed&amp;display_name=Embed+Fun&amp;src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FbjFHti6uHtqr26pEqH6T2" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/20b0e0ffe225f8a7c46cd0f5e014c6f5/href">https://medium.com/media/20b0e0ffe225f8a7c46cd0f5e014c6f5/href</a></iframe><p>The estimated probabilities constitute the interesting part of the result: we can use them for visualisation and even future classification.</p><h3>Conclusions and Further Directions</h3><p>I mentioned a generative statistical model, <em>P</em>. The algorithm does not specify its nature, so the <a href="https://en.wikipedia.org/wiki/EM_algorithm_and_GMM_model">Gaussian Mixture Model</a> is <strong>not</strong> the only model it applies to. <em>P</em> can be a family of probabilistic graphical models — then the maximisation becomes intractable, but small improvements are computationally feasible.</p><p>Here is the homework for you:</p><ul><li>Prove that applying Bayes&#39; rule does not introduce infinities into the expression.</li><li>Implement the EM Algorithm for the classical <a href="https://en.wikipedia.org/wiki/EM_algorithm_and_GMM_model">Gaussian Mixture Model</a> example. What happens if multiple clusters share the same centroid?</li><li>Implement a generic EM Algorithm that accepts an arbitrary generative model and maximisation procedure. How do you handle the machine-zero issue when averaging generally?</li><li>Apply the EM Algorithm to a problem involving Markov Chains (so the Maximisation step requires <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">dynamic programming</a>) — this particular case of the algorithm is also known as the <a href="https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm">Baum-Welch algorithm</a>.</li><li>Read <a href="https://doi.org/10.1007/978-94-017-3217-8">Ten Lectures on Statistical and Structural Pattern Recognition</a> (or at least <a href="https://doi.org/10.1007/BF01073742">The interaction of learning and self-organization in pattern recognition</a>).</li><li>Find and understand the proofs of the <a href="https://en.wikipedia.org/wiki/Lagrange_multiplier">method of Lagrange multipliers</a> and <a href="https://en.wikipedia.org/wiki/Gibbs%27_inequality">Gibbs’ inequality</a>.</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f0a39a10e704" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[C++26: Bye-Bye Raw Pointers?]]></title>
            <link>https://medium.com/@valeriy.krygin/c-26-bye-bye-raw-pointers-764d87f600b1?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/764d87f600b1</guid>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[c-plus-plus-language]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Sun, 01 Mar 2026 10:49:03 GMT</pubDate>
            <atom:updated>2026-06-30T17:06:26.126Z</atom:updated>
            <content:encoded><![CDATA[<h4>How close is C++ to memory safety?</h4><p>With the great power of <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers">pointers</a> comes the great responsibility of memory safety. The responsibility is so great that the Cybersecurity and Infrastructure Security Agency (CISA) explicitly recommends against using C or C++ in certain circumstances (see <a href="https://www.cisa.gov/resources-tools/resources/product-security-bad-practices">Product Security Bad Practices</a> for more information). However, I argue that there is hope for modern C++.</p><p><em>If you are here after a concise answer, simply jump to the </em><a href="#79e5"><em>Conclusion</em></a><em>.</em></p><h3>Table of Contents</h3><ul><li><a href="#1c9a">Introduction</a></li><li><a href="#d4f8">Allocation and Deallocation</a></li><li><a href="#c92d">Null Pointer</a></li><li><a href="#5ee0">Pointers to Members</a></li><li><a href="#0b92">Pointers to Functions</a></li><li><a href="#4859">Dynamic Polymorphism</a></li><li><a href="#79e5">Conclusion and Further Directions</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g2nf19KIX-pDnB--Ay2f4w.png" /><figcaption>Picture by the Author</figcaption></figure><h3>Introduction</h3><p>A <a href="https://en.wikipedia.org/wiki/Pointer_(computer_programming)">pointer</a> is a variable containing an address in memory (for example, RAM or VRAM). It lets you access data and processor instructions in memory to read, modify, or even execute them. However, data manipulation and instruction execution are exactly the purpose of computers, right? Well, the possibility of doing this through pointers does not mean you should use pointers intensively in modern C++. Why? <a href="https://media.defense.gov/2023/Dec/06/2003352724/-1/-1/0/THE-CASE-FOR-MEMORY-SAFE-ROADMAPS-TLP-CLEAR.PDF">The Case for Memory Safe Roadmaps</a> mentions the following problems:</p><ul><li><a href="https://cwe.mitre.org/data/definitions/120.html">buffer overflow</a>;</li><li><a href="https://cwe.mitre.org/data/definitions/416.html">use after free</a>;</li><li><a href="https://cwe.mitre.org/data/definitions/908.html">use of uninitialised memory</a>;</li><li><a href="https://cwe.mitre.org/data/definitions/415.html">double free</a>.</li></ul><p>Scary, are they not? Let us examine the causes of issues arising from the use of <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers">raw pointers</a> and how we can address them in modern C++.</p><h3>Allocation and Deallocation</h3><p>One of the scariest things for those starting to learn <a href="https://en.cppreference.com/w/cpp/language/history.html#C.2B.2B98.2F03_period">C++98/03</a> is allocating and deallocating memory. There is something about understanding the difference between <a href="https://en.cppreference.com/w/cpp/memory/new/operator_new">operator new[]</a> and <a href="https://en.cppreference.com/w/cpp/memory/new/operator_new">operator new</a> (with and without square brackets), using <a href="https://en.cppreference.com/w/cpp/memory/new/operator_delete.html">operator delete[]</a> and <a href="https://en.cppreference.com/w/cpp/memory/new/operator_delete.html">operator delete</a> correctly, not mixing them with <a href="https://en.cppreference.com/w/cpp/memory/c/malloc.html">std::malloc</a> and <a href="https://en.cppreference.com/w/cpp/memory/c/free.html">std::free</a>, and realising the existence of <a href="https://en.cppreference.com/w/cpp/memory/c/calloc.html">std::calloc</a> and <a href="https://en.cppreference.com/w/cpp/memory/c/realloc.html">std::realloc</a>. Do you remember messing with destructors to avoid <a href="https://cwe.mitre.org/data/definitions/415.html">double freeing</a>, trying to understand why <a href="https://cwe.mitre.org/data/definitions/401.html">memory leaks</a> are undesirable, and other [big] nuances of memory management?</p><p>Since the beginning of C++, we have standard containers such as <a href="https://en.cppreference.com/w/cpp/container/vector.html">std::vector</a>, <a href="https://en.cppreference.com/w/cpp/container/map.html">std::map</a>, <a href="https://en.cppreference.com/w/cpp/container/list.html">std::list</a>, and <a href="https://en.cppreference.com/w/cpp/container/deque.html">std::deque</a>, among many others. Since <a href="https://en.cppreference.com/w/cpp/11.html">C++11</a>, we have <a href="https://en.cppreference.com/w/cpp/memory/shared_ptr.html">std::shared_ptr</a>, <a href="https://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr</a>, and <a href="https://en.cppreference.com/w/cpp/memory/weak_ptr.html">std::weak_ptr</a> as well as <a href="https://en.cppreference.com/w/cpp/memory/shared_ptr/make_shared.html">std::make_shared</a>; since <a href="https://en.cppreference.com/w/cpp/14.html">C++14</a>, we have <a href="https://en.cppreference.com/w/cpp/memory/unique_ptr/make_unique.html">std::make_unique</a>. These classes allow you to rely on <a href="https://en.cppreference.com/w/cpp/language/raii.html">RAII</a> to guarantee proper memory freeing.</p><p>Why do we still need smart pointers if we have containers? They are useful for a <a href="https://en.cppreference.com/w/cpp/language/pimpl.html">pointer to implementation</a>, also known as the <a href="https://en.cppreference.com/w/cpp/language/pimpl.html">PImpl</a> idiom. It enables data hiding and saves compilation time by incurring runtime overhead. Also, <a href="https://en.cppreference.com/w/cpp/memory/unique_ptr.html">std::unique_ptr</a> ensures single ownership — it does not allow copying objects that must not be copied.</p><p>Bye-bye manual memory allocation and deallocation!</p><h3>Null Pointer</h3><p>The canonical way to avoid the <a href="https://qconlondon.com/london-2009/qconlondon.com/london-2009/presentation/Null%2BReferences_%2BThe%2BBillion%2BDollar%2BMistake.html">infamous null pointer exception</a> in C++ is to use <a href="https://en.cppreference.com/w/cpp/language/reference.html">references</a>, which have been available since the beginning of C++ (Lvalue references; Rvalue references were introduced in <a href="https://en.cppreference.com/w/cpp/11.html">C++11</a>). You cannot create a reference without a “host”, so there is no such thing as a null reference in C++. Nonetheless, there are <a href="https://en.cppreference.com/w/cpp/language/reference.html#Dangling_references">dangling references</a>, usually due to ownership issues, which can be resolved with <a href="https://en.cppreference.com/w/cpp/memory/shared_ptr.html">std::shared_ptr</a> or <a href="https://en.cppreference.com/w/cpp/memory/weak_ptr.html">std::weak_ptr</a>. However, a smart pointer can contain a <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Null_pointers">null pointer</a>.</p><h4>Tip 1: Use Constant Smart Pointers</h4><p>To prevent a smart pointer from being accidentally released, use <a href="https://en.cppreference.com/w/cpp/language/cv.html">const</a> if possible. In this case, you cannot use <a href="https://en.cppreference.com/w/cpp/memory/shared_ptr/reset.html">std::shared_ptr::release</a> or <a href="https://en.cppreference.com/w/cpp/memory/unique_ptr/reset.html">std::unique_ptr::release</a>, and you must initialise the pointers immediately. Thus, if you do any of the following:</p><pre>// Explicitly wrap a null pointer<br>const std::unique_ptr&lt;T&gt; a{nullptr};<br>// Use the default constructor, which wraps a null pointer<br>const std::unique_ptr&lt;T&gt; b;<br><br>struct A<br>{<br>  // Note: constant unique pointer<br>  // makes the structure uncopiable and unmovable<br>  const std::unique_ptr&lt;T&gt; c;<br>};<br>// The default constructor of A<br>// triggers the default constructors of its members.<br>// You cannot do a.c = std::make_unique&lt;T&gt;(/* parameters */);<br>// because `A::c` is `const`.<br>A a;</pre><p>you already know where to look for an issue.</p><h4>Tip 2: Use Containers</h4><p>You can avoid trying to dereference a <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Null_pointers">null pointer</a> in standard containers like <a href="https://en.cppreference.com/w/cpp/container/vector.html">std::vector</a>, <a href="https://en.cppreference.com/w/cpp/container/map.html">std::map</a>, <a href="https://en.cppreference.com/w/cpp/container/deque.html">std::deque</a>, <a href="https://en.cppreference.com/w/cpp/container/unordered_map.html">std::unordered_map</a> and so on, using the at member function instead of operator[]. It checks whether the positive index is out of positive bounds; you still need to ensure the index is non-negative — for example, by using unsigned <a href="https://en.cppreference.com/w/cpp/language/types.html#Integral_types">integral types</a>. Thus, using <a href="https://en.cppreference.com/w/cpp/language/range-for.html">range-based for loops</a> since <a href="https://en.cppreference.com/w/cpp/11.html">C++11</a> is even better! If you do not need to iterate through all elements of a range/container, look at the <a href="https://en.cppreference.com/w/cpp/ranges.html">ranges library</a> introduced with <a href="https://en.cppreference.com/w/cpp/20.html">C++20</a>. Also, take a look at the <a href="https://en.cppreference.com/w/cpp/algorithm.html">algorithms library</a>: there are very useful algorithms since the first C++ standards, and they may have already implemented the operations you want to perform on your collection of elements.</p><p>There are also containers you can use if you know the number of elements at compile time, or even better, if you can create the containers at compile time: <a href="https://en.cppreference.com/w/cpp/container/array.html">std::array</a> if all elements are of the same type and <a href="https://en.cppreference.com/w/cpp/utility/tuple.html">std::tuple</a> if they are not. Remember to use <a href="https://en.cppreference.com/w/cpp/container/array/get.html">std::get(std::array)</a> and <a href="https://en.cppreference.com/w/cpp/utility/tuple/get.html">std::get(std::tuple)</a> whenever possible (you can even assign with std::get&lt;N&gt;(myArray) = value;); they provide compile-time bounds checking, keeping your code safer.</p><h4>Tip 3: Use <a href="https://en.cppreference.com/w/cpp/utility/optional.html">std::optional</a></h4><p>This <a href="https://en.cppreference.com/w/cpp/17.html">C++17</a> feature is very handy for a common use case of non-const pointers: holding a value that may or may not exist. Technically, this is also a container, but not as famous as, for example, <a href="https://en.cppreference.com/w/cpp/container/vector.html">std::vector</a>.</p><p>You may have seen (and used) the following approaches:</p><pre>#include &lt;memory&gt;<br>#include &lt;string&gt;<br>#include &lt;string_view&gt;<br><br>using std::literals::string_view_literals::operator&quot;&quot;sv;<br><br>enum class E<br>{<br>  // Using `none` enumeration element looks solid and innocent.<br>  // However, `x == E::none` is your null reference check now.<br>  none,<br>  red,<br>  green,<br>};<br><br>struct A<br>{<br>  std::string getString() const<br>  {<br>    // Treating an empty string as no string at all<br>    // may look right sometimes.<br>    // However, what if you do start using empty strings?<br>    return s.empty() ? std::string{defaultS} : s;<br>  }<br>  int getInt() const<br>  {<br>    // Feels just like a raw pointer<br>    return i ? defaultI : *i;<br>  }<br>  E getEnum() const<br>  {<br>    return e;<br>  }<br><br>  void append(const std::string&amp; value)<br>  {<br>    // Looks tempting<br>    if (!s.empty())<br>    {<br>      s += value;<br>    }<br>  }<br>  void add(const int value)<br>  {<br>    // Looks old-fashioned yet solid<br>    if (i)<br>    {<br>      *i += value;<br>    }<br>  }<br>  void toggle()<br>  {<br>    switch (e)<br>    {<br>      case E::none:<br>        break;<br>      case E::red:<br>        e = E::green;<br>        break;<br>      case E::green:<br>        e = E::red;<br>        break;<br>    }<br>  }<br><br>  std::string s;<br>  std::unique_ptr&lt;int&gt; i;<br>  E e{E::none};<br><br>  static constexpr auto defaultS{&quot;No value&quot;sv};<br>  static constexpr int defaultI{-1};<br>};</pre><p>It works. It is even somehow intuitive. What is the problem? If you check whether <a href="https://en.cppreference.com/w/cpp/string/basic_string.html">std::basic_string</a> or any other container is empty to consider it not bearing a value at all, you will have to redesign your code once an empty container is a valid value. If you use an enumeration, you can add none as an empty value; however, checking it would be similar to checking a null pointer. If you use pointers directly, you still have to check that they are not <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Null_pointers">null</a> and initialise them correctly when needed.</p><p>I strongly recommend using <a href="https://en.cppreference.com/w/cpp/utility/optional.html">std::optional</a>, which was designed exactly for this use case, unless you desperately need to save space and time overheads it provides. First, you can use <a href="https://en.cppreference.com/w/cpp/utility/optional/value_or.html">std::optional::value_or</a> to fetch the default value if there is no contained value. Second, <a href="https://en.cppreference.com/w/cpp/23.html">C++23</a> introduces <a href="https://en.cppreference.com/w/cpp/utility/optional/transform.html">std::optional::transform</a> to transform the contained value (if one exists) safely and do nothing otherwise.</p><pre>#include &lt;optional&gt;<br>#include &lt;string&gt;<br>#include &lt;string_view&gt;<br><br>using std::literals::string_view_literals::operator&quot;&quot;sv;<br><br>enum class E<br>{<br>  red,<br>  green,<br>};<br><br>struct A<br>{<br>  std::string getString() const<br>  {<br>    // The intention of this operation is clear<br>    return s.value_or(std::string{defaultS});<br>  }<br>  int getInt() const<br>  {<br>    // The intention of this operation is clear<br>    return i.value_or(defaultI);<br>  }<br>  // It is okay to let others know<br>  // that the value may not exist and there is no default one<br>  std::optional&lt;E&gt; getEnum() const<br>  {<br>    return e;<br>  }<br><br>  void append(const std::string&amp; value)<br>  {<br>    // If `s` is `std::nullopt`,<br>    // it will still be `std::nullopt` without any issues<br>    s = s.transform([&amp;value](auto&amp;&amp; currentValue)<br>      {<br>        return currentValue + value;<br>      }<br>    );<br>  }<br>  void add(const int value)<br>  {<br>    // If `i` is `std::nullopt`,<br>    // it will still be `std::nullopt` without any issues<br>    i = i.transform([&amp;value](auto&amp;&amp; currentValue)<br>      {<br>        return currentValue + value;<br>      }<br>    );<br>  }<br>  void toggle()<br>  {<br>    e = e.and_then([](auto&amp;&amp; currentValue) -&gt; std::optional&lt;E&gt;<br>      {<br>        switch (currentValue)<br>        {<br>          case E::red:<br>            return E::green;<br>          case E::green:<br>            return E::red;<br>          default:<br>            // While we use `std::optional` safely,<br>            // it is completely fine to store `std::nullopt`.<br>            return std::nullopt;<br>        }<br>      }<br>    );<br>  }<br><br>  std::optional&lt;std::string&gt; s;<br>  std::optional&lt;int&gt; i;<br>  std::optional&lt;E&gt; e;<br><br>  static constexpr auto defaultS{&quot;No value&quot;sv};<br>  static constexpr int defaultI{-1};<br>};</pre><p>Why is this better? First of all, it is explicit: it tells all developers that these values may exist (not must). Second, there are member functions designed to solve the “null pointer” issue: you should not call <a href="https://en.cppreference.com/w/cpp/utility/optional/operator_bool.html">std::optional::has_value</a> before every attempt to read a value. Instead, you can use <a href="https://en.cppreference.com/w/cpp/utility/optional/value_or.html">std::optional::value_or</a> to access a value if there is one or get a default if applicable, <a href="https://en.cppreference.com/w/cpp/utility/optional/transform.html">std::optional::transform</a> to get an <a href="https://en.cppreference.com/w/cpp/utility/optional.html">std::optional</a> with a modified value or <a href="https://en.cppreference.com/w/cpp/utility/optional/nullopt.html">std::nullopt</a> if there was no value. There are also <a href="https://en.cppreference.com/w/cpp/utility/optional/and_then.html">std::optional::and_then</a> and <a href="https://en.cppreference.com/w/cpp/utility/optional/or_else.html">std::optional::or_else</a> for more chaining possibilities. Keep in mind that <a href="https://en.cppreference.com/w/cpp/utility/optional.html">std::optional</a> adds compile-time and runtime overhead, so you have to choose wisely between safety and performance.</p><p>Bye-bye null pointer dereferencing!</p><h3>Pointers to Members</h3><p>You may not have heard of this, but <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_members">pointers to members</a> are useful when you want to guarantee that a function operates exactly on the class members, not on arbitrary variables or functions. Unfortunately, these are still ordinary pointers, and there is not much we can do about them at runtime, even with <a href="https://isocpp.org/files/papers/P2996R4.html#meta.reflection.trans.ptr-pointer-modifications">C++26 Reflection</a>.</p><p>Let us come up with an example — a getter for public members:</p><pre>struct A<br>{<br>  int get(const int A::* const member) const<br>  {<br>    return this-&gt;*member;<br>  }<br><br>  int a;<br>};</pre><p>You can use it like this:</p><pre>const A a{.a = -1};<br>std::cout &lt;&lt; a.get(&amp;A::a) &lt;&lt; std::endl;</pre><p>In this example, the last line of code is equivalent to std::cout &lt;&lt; a.a &lt;&lt; std::endl;. The problem is, you can use a.get(nullptr) and get into trouble.</p><p>Why would anybody want to complicate things so much? As I said before, sometimes you want compile-time guarantees that a function operates solely on non-static <a href="https://en.cppreference.com/w/cpp/language/data_members.html">data members</a> or <a href="https://en.cppreference.com/w/cpp/language/member_functions.html">member functions</a> of a specific class. Can we ensure this trait without using pointers? I think not yet, not as per <a href="https://en.cppreference.com/w/cpp/26.html">C++26</a>. Can we ensure their safe use? Only in compile time. We can modify the example above as follows:</p><pre>struct A<br>{<br>  template&lt;int A::* member&gt; int get() const<br>  {<br>    return this-&gt;*member;<br>  }<br><br>  int a;<br>};</pre><p>and use it as</p><pre>const A a{.a = -1};<br>std::cout &lt;&lt; a.get&lt;&amp;A::a&gt;() &lt;&lt; std::endl;</pre><p>In such a case, you cannot provide <a href="https://en.cppreference.com/w/cpp/language/nullptr.html">nullptr</a> as the argument accidentally. You decide what introduces greater risk to the system: the possibility of providing an argument from an undesired source (for example, a member from another class) or the possibility that somebody forgets to validate the function input.</p><p>Long live <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_members">pointers to members</a>!</p><h3>Pointers to Functions</h3><p>You can use <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_functions">function pointers</a> for callbacks or to generalise algorithms. For example, let us consider a function that accepts a collection of integers and a predicate that finds the first integer satisfying the predicate:</p><pre>#include &lt;span&gt;<br><br>bool find(std::span&lt;const int&gt; values, bool (*predicate)(int))<br>{<br>  for (auto&amp;&amp; value : values)<br>  {<br>    if (predicate(value))<br>    {<br>      return true;<br>    }<br>  }<br>  return false;<br>}</pre><p>There is a huge problem: if we call it like find(values, nullptr);, the application usually crashes. The obvious solution is to add a <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Null_pointers">null pointer</a> check. However, if it were so obvious, we would unlikely to see the title “<a href="https://qconlondon.com/london-2009/qconlondon.com/london-2009/presentation/Null%2BReferences_%2BThe%2BBillion%2BDollar%2BMistake.html">Null References: The Billion Dollar Mistake</a>” by Tony Hoare, who, as far as I could check, invented null reference.</p><h4>Solution 1: Lambda Expressions</h4><p>It is safe to use <a href="https://en.cppreference.com/w/cpp/language/lambda.html">lambda expressions</a> instead of function pointers. However, the definition of the <a href="https://en.cppreference.com/w/cpp/language/function_template.html">function template</a> that accepts a <a href="https://en.cppreference.com/w/cpp/language/lambda.html">lambda</a> as an argument must be available to the caller; <a href="https://en.cppreference.com/w/cpp/26.html">C++20</a> <a href="https://en.cppreference.com/w/cpp/language/modules.html">modules</a> could fix this, but we have yet to see them fully functional as of 2026. In the following example, using the <a href="https://en.cppreference.com/w/cpp/26.html">C++20</a> <a href="https://en.cppreference.com/w/cpp/language/constraints.html">concept</a> <a href="https://en.cppreference.com/w/cpp/concepts/predicate.html">std::predicate</a> is not required, but adds clarity and safety:</p><pre>#include &lt;concepts&gt;<br>#include &lt;span&gt;<br><br>template&lt;typename Predicate&gt;<br>requires std::predicate&lt;Predicate, int&gt;<br>bool find(const std::span&lt;const int&gt; values, Predicate predicate)<br>{<br>  for (auto&amp;&amp; value : values)<br>  {<br>    if (predicate(value))<br>    {<br>      return true;<br>    }<br>  }<br>  return false;<br>}</pre><p>This resembles the behaviour of functions from the <a href="https://en.cppreference.com/w/cpp/algorithm.html">standard algorithms library</a>. You can use it as follows:</p><pre>bool containsZero(const std::vector&lt;int&gt;&amp; input)<br>{<br>  return find(input, [](const auto&amp; element) { return element == 0; });<br>}</pre><h4>Solution 2: Function Wrapper</h4><p>If you cannot use <a href="https://en.cppreference.com/w/cpp/language/lambda.html">lambda expressions</a> for whatever reason (the reason is better to be good), another possible <a href="https://en.cppreference.com/w/cpp/11.html">C++11</a> solution is to use <a href="https://en.cppreference.com/w/cpp/utility/functional/function.html">std::function</a> instead of a <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_functions">raw pointer</a>:</p><pre>#include &lt;functional&gt;<br>#include &lt;span&gt;<br><br>bool find(std::span&lt;const int&gt; values, std::function&lt;bool(int)&gt; predicate)<br>{<br>  for (auto&amp;&amp; value : values)<br>  {<br>    if (predicate(value))<br>    {<br>      return true;<br>    }<br>  }<br>  return false;<br>}</pre><p>You can still provide a <a href="https://en.cppreference.com/w/cpp/language/nullptr.html">nullptr</a> instead of a function. However, instead of crashing, the code <a href="https://en.cppreference.com/w/cpp/utility/functional/function/operator().html#Exceptions">throws an exception</a> that you can <a href="https://en.cppreference.com/w/cpp/language/catch.html">catch</a>. This means that, even if you forgot to check the argument and forgot to surround the function with <a href="https://en.cppreference.com/w/cpp/language/catch.html#Matching_exceptions">try-catch</a>, you still have:</p><ul><li><a href="https://en.cppreference.com/w/cpp/language/raii.html">RAII</a> that guarantees all required destructors are called;</li><li>the possibility of catching the exception at a higher level by specifically hunting for <a href="https://en.cppreference.com/w/cpp/utility/functional/bad_function_call.html">std::bad_function_call</a> or by catching its parent, <a href="https://en.cppreference.com/w/cpp/error/exception.html">std::exception</a>, or by using a wildcard catch(…).</li></ul><p>Bye-bye <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_functions">pointers to functions</a>! Except for the <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_member_functions">pointers to member functions</a>.</p><h3>Dynamic Polymorphism</h3><p>While every C++ developer has heard (and hopefully used!) references, standard containers, and smart pointers, there is still a major feature that lacked its dedicated container until <a href="https://en.cppreference.com/w/cpp/26.html">C++26</a> — runtime polymorphism. It is quite interesting, given that C++ was introduced as <a href="https://www.stroustrup.com/classes_1982.pdf">C with classes</a>, and that polymorphism is a fundamental concept in object-oriented programming.</p><h4>Method 1: Smart Pointer</h4><p>You may need to use a smart pointer at some point if you work with dynamic polymorphism:</p><pre>#include &lt;memory&gt;<br><br>struct Base<br>{<br>  virtual ~Base() = default;<br>};<br><br>struct DerivedA : Base<br>{<br>  ~DerivedA() override = default;<br>};<br><br>struct DerivedB : Base<br>{<br>  ~DerivedB() override = default;<br>};<br><br>enum class Choice<br>{<br>  A,<br>  B,<br>};<br><br>std::unique_ptr&lt;Base&gt; produce(const Choice choice)<br>{<br>  switch (choice)<br>  {<br>    case Choice::A:<br>      // Please do not do it like this.<br>      // It is possible because the constructor of std::unique_ptr is noexcept,<br>      // but we already have modern C++.<br>      return std::unique_ptr&lt;Base&gt;(new DerivedA);<br>    case Choice::B:<br>      // unique_ptr&lt;DerivedB&gt; is implicitly convertible to unique_ptr&lt;Base&gt;<br>      // because DerivedB is a derived class of Base<br>      return std::make_unique&lt;DerivedB&gt;();<br>    default:<br>      return {};<br>  }<br>}</pre><p>A smart pointer in this case looks like a nice solution:</p><ul><li>You have your runtime polymorphism.</li><li>The smart pointer’s destructor handles memory deallocation.</li><li><a href="https://en.cppreference.com/w/cpp/language/raii.html">RAII</a> ensures destructors are called to prevent memory leaks.</li></ul><p>However, Smart pointers may contain <a href="https://en.cppreference.com/w/cpp/language/nullptr.html">nullptr</a>. Checking whether this happens is up to the developers. Thus, it may mean the value is optional; more often than not, I need a mandatory value.</p><h4>Method 2: C++26 <a href="https://en.cppreference.com/w/cpp/memory/polymorphic.html">std::polymorphic</a></h4><p>Like <a href="https://en.cppreference.com/w/cpp/utility/optional.html">std::optional</a> is a special tool for handling values that may not exist, <a href="https://en.cppreference.com/w/cpp/memory/polymorphic.html">std::polymorphic</a> is designed to handle runtime polymorphism.</p><pre>#include &lt;memory&gt;<br><br>struct Base<br>{<br>  virtual ~Base() = default;<br>};<br><br>struct DerivedA : Base<br>{<br>  ~DerivedA() override = default;<br>};<br><br>struct DerivedB : Base<br>{<br>  ~DerivedB() override = default;<br>};<br><br>enum class Choice<br>{<br>  A,<br>  B,<br>};<br><br>std::polymorphic&lt;Base&gt; produce(const Choice choice)<br>{<br>  switch (choice)<br>  {<br>    case Choice::A:<br>      // The following line of code<br>      // explicitly calls the default constructor of DerivedA.<br>      // Then, it triggers the move constructor of DerivedA.<br>      // Not very efficient.<br>      return std::polymorphic&lt;Base&gt;{DerivedA{}};<br>    case Choice::B:<br>      // This is better: the DerivedB object will be created<br>      // inside the polymoprhic constructor<br>      return std::polymorphic&lt;Base&gt;{std::in_place_type&lt;DerivedB&gt;};<br>    default:<br>      // This is not a null reference.<br>      // This is a default-constructed Base object.<br>      // No implicit optional values!<br>      return std::polymorphic&lt;Base&gt;{};<br>  }<br>}</pre><p>Why is <a href="https://en.cppreference.com/w/cpp/memory/polymorphic.html">std::polymorphic</a> better than smart pointers for storing polymorphic objects:</p><ol><li><a href="https://en.cppreference.com/w/cpp/memory/polymorphic.html">std::polymorphic&lt;T&gt;</a> signals the developers explicitly, “The value here may be of any type compatible with T;”</li><li>If the value should be optional, you can tell this explicitly: std::optional&lt;std::polymorphic&lt;T&gt;&gt;.</li><li>Although <a href="https://en.cppreference.com/w/cpp/memory/polymorphic.html">std::polymorphic</a> can hold a “null pointer” (be valueless), which can be checked by <a href="https://en.cppreference.com/w/cpp/memory/polymorphic/valueless_after_move.html">std::polymorphic::valueless_after_move</a>, this situation occurs after a move constructor is called (just like the name suggests) and, consequently, when constructing from a valueless object. Usually, you do not perform actions on objects you move-d anyways.</li></ol><p>Look at this example:</p><pre>#include &lt;iostream&gt;<br>#include &lt;ios&gt;<br><br>int main()<br>{<br>  std::cout &lt;&lt; std::boolalpha;<br>  auto x = produce(Choice::A);<br>  std::cout &lt;&lt; &quot;After producing x:&quot; &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  x valuessness: &quot; &lt;&lt; x.valueless_after_move() &lt;&lt; std::endl;<br>  auto y = std::move(x);<br>  std::cout &lt;&lt; &quot;After moving x to y:&quot; &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  x valuessness: &quot; &lt;&lt; x.valueless_after_move() &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  y valuessness: &quot; &lt;&lt; y.valueless_after_move() &lt;&lt; std::endl;<br>  <br>  auto z = std::move(x);<br>  std::cout &lt;&lt; &quot;After moving x to z:&quot; &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  x valuessness: &quot; &lt;&lt; x.valueless_after_move() &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  y valuessness: &quot; &lt;&lt; y.valueless_after_move() &lt;&lt; std::endl;<br>  std::cout &lt;&lt; &quot;  z valuessness: &quot; &lt;&lt; z.valueless_after_move() &lt;&lt; std::endl;<br>  return 0;<br>}</pre><p>The expected output is</p><pre>After producing x:<br>  x valuessness: false<br>After moving x to y:<br>  x valuessness: true<br>  y valuessness: false<br>After moving x to z:<br>  x valuessness: true<br>  y valuessness: false<br>  z valuessness: true</pre><p>You can play with the <a href="https://godbolt.org/z/e9xjs8Khs">example</a> in Compiler Explorer. Feel free to modify it as you wish: once you open the code, you have your own copy, and your changes will not affect the example I provided here.</p><p>Bye-bye <a href="https://en.cppreference.com/w/cpp/memory/new/operator_new">operator new</a> and smart pointers for runtime polymorphism!</p><h3>Conclusion and Further Directions</h3><p>In short,<br>Bye-bye raw pointers? No.<br>Bye-bye problems caused by raw pointers? No.</p><p>Nevertheless, I have hope and strong beliefs about codebases that rely on high-level language features and can afford upgrades to modern C++ versions, which I describe below.</p><h4>Bye-bye raw pointers?</h4><p>Why not:</p><ul><li>communication with C or legacy code, or with libraries aiming to preserve a high language compatibility (for example, <a href="https://github.com/ocornut/imgui">Dear ImGui</a>);</li><li><a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_members">pointers to members</a> (partially solved by <a href="https://en.cppreference.com/w/cpp/26.html">C++26</a> <a href="https://isocpp.org/files/papers/P2996R4.html">compile-time reflection</a>).</li></ul><p>Solutions to other problems:</p><ul><li>containers;</li><li>safe iteration over containers (<a href="https://en.cppreference.com/w/cpp/11.html">C++11</a>);</li><li>function wrappers and lambdas (<a href="https://en.cppreference.com/w/cpp/11.html">C++11</a>);</li><li>smart pointers (<a href="https://en.cppreference.com/w/cpp/11.html">C++11</a>);</li><li>optional values (<a href="https://en.cppreference.com/w/cpp/17.html">C++17</a>);</li><li>polymorphic types (<a href="https://en.cppreference.com/w/cpp/26.html">C++26</a>).</li></ul><h4>Bye-bye problems caused by raw pointers?</h4><p>The major problem with pointers in C++ is error handling. When you <a href="https://en.cppreference.com/w/c/language/operator_member_access.html#Dereference">dereference</a> a <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Null_pointers">null pointer</a>, the behaviour is <a href="https://en.cppreference.com/w/cpp/language/ub.html">undefined</a>, but it usually causes the program to crash, which cannot be tested using <a href="https://en.cppreference.com/w/cpp/language/catch.html#Matching_exceptions">try-catch</a>. In modern C++, we can avoid the dereferencing problem by</p><ul><li>avoiding raw pointers as described in this story;</li><li>using at(index) member function of containers to trigger an exception in the case when the index is not available (except for negative ones), or std::get&lt;I&gt; for fixed-size collections to ensure compile-time boundary check;</li><li>using <a href="https://en.cppreference.com/w/cpp/language/range-for.html">range-based for loops</a>, <a href="https://en.cppreference.com/w/cpp/algorithm.html">algorithms library</a>, or <a href="https://en.cppreference.com/w/cpp/ranges.html">ranges library</a> to iterate over containers;</li><li>using constant smart pointers to initialise them immediately and safely avoid the necessity of null pointer checks;</li><li>using <a href="https://en.cppreference.com/w/cpp/language/template_parameters.html#Constant_template_parameter">non-type template parameters</a> to ensure compile-time correctness check.</li></ul><p>Nevertheless, <a href="https://en.cppreference.com/w/cpp/26.html">C++26</a> still contains the danger of null pointer dereferencing:</p><ul><li>calls to third-party functions that use <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers">raw pointers</a>;</li><li>non-constant smart pointers can become <a href="https://en.cppreference.com/w/cpp/language/nullptr.html">nullptr</a> at any moment (especially in a multi-threaded environment);</li><li><a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_members">pointers to members</a> are still <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers">raw pointers</a>;</li><li><a href="http://dangling_references/">dangling references</a>.</li></ul><h4>Is there hope?</h4><p>With each standard, C++ becomes safer for day-to-day tasks. Of course, if your job involves low-level programming, performance-critical programming, or managing bindings, or you cannot or do not use the modern C++ features or cannot switch to another language, you probably have to use raw pointers. If you have the luxury of jumping to the latest standards and concentrating on higher-level C++ coding, there is a light at the end of the tunnel.</p><p>Where do I see the hope? In my opinion, to cover the concerns outlined in this story, C++ lacks just a few more things:</p><ul><li>real-time reflection (<a href="https://en.cppreference.com/w/cpp/26.html">C++26</a> should introduce <a href="https://isocpp.org/files/papers/P2996R13.html">compile-time reflection</a>) to avoid <a href="https://en.cppreference.com/w/cpp/language/pointer.html#Pointers_to_members">pointers to members</a>;</li><li>smart pointers with runtime checks and <a href="https://en.cppreference.com/w/cpp/language/exceptions.html">exceptions</a> instead of <a href="https://en.cppreference.com/w/cpp/language/ub.html">undefined behaviour</a>.</li></ul><p>A note about the story&#39;s author (me): I code in modern C (<a href="https://en.cppreference.com/w/c/23.html">C23</a>) in my spare time, and C++ was my first programming language. Thus, <a href="https://en.cppreference.com/w/c/language/pointer.html">raw pointers</a> are forever in my heart.</p><h4>Questions</h4><ul><li>What major use-cases of raw pointers did I miss?</li><li>What major issues with raw pointers did I not cover?</li><li>What other solutions to the mentioned problems can you recommend?</li><li>What should we do with <a href="http://dangling_references/">dangling references</a>?</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=764d87f600b1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Perceptron. Part 2: The Story Untold]]></title>
            <link>https://medium.com/@valeriy.krygin/perceptron-part-2-the-story-untold-a05029c2629d?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/a05029c2629d</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[ellipse]]></category>
            <category><![CDATA[normal-distribution]]></category>
            <category><![CDATA[perceptron]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Fri, 01 Nov 2024 11:50:39 GMT</pubDate>
            <atom:updated>2024-11-01T12:28:55.746Z</atom:updated>
            <content:encoded><![CDATA[<h4>Gaussian Vectors Classification</h4><p>Stories of the series:</p><ul><li><a href="https://medium.com/@valeriy.krygin/perceptron-part-1-the-story-retold-2065c341b60d">Perceptron. Part 1: The Story Retold</a></li><li><a href="https://medium.com/@valeriy.krygin/perceptron-part-2-the-story-untold-a05029c2629d">Perceptron. Part 2: The Story Untold</a></li></ul><p>Source code: definability/perceptron_ellipse. I license the code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it.</p><h3>Table of Contents</h3><ul><li><a href="#b48b">Introduction</a></li><li><a href="#003d">The Problem</a><br>- <a href="#b79c">Fetching Ellipse Formula</a><br>- <a href="#44a2">Problem Linearisation</a><br>- <a href="#78f8">Matrix Eigendecomposition</a><br>- <a href="#33ee">Consistency</a></li><li><a href="#cdef">The Algorithm</a><br>- <a href="#8ce9">Initialisation</a><br>- <a href="#8ce9">Training</a><br>- <a href="#f292">Ensuring Positive Definiteness</a><br>- <a href="#9b7a">Ensuring Consistency</a></li><li><a href="#8ec0">Conclusions and Further Directions</a></li></ul><h3>Introduction</h3><p>The perceptron algorithm is used to train linear classifiers. If you do not know how it does it or whether it is guaranteed to converge, find it out in <a href="https://medium.com/@valeriy.krygin/perceptron-part-1-the-story-retold-2065c341b60d">Perceptron. Part 1: The Story Retold</a>. However, the basic ideas of the algorithm apply to a wide variety of situations, even if they are not linear and sometimes look absurd. This story is dedicated to classifying Gaussian vectors: given a set of vectors, we want to know which ones belong to the specific region of a multivariate Gaussian distribution. However, instead of explicitly specifying the parameters of the multivariate normal distribution, we have two sets of vectors: one containing those belonging to the region of interest and another containing those not belonging. See the picture below for a visualisation of the problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cjG1ZamXnkB4Xle8k0wVYw.png" /><figcaption>Separation with a Gaussian distribution isoline using a modified linear classifier. Picture by the Author.</figcaption></figure><p>I learnt this algorithm&#39;s basics from <a href="https://dl.acm.org/profile/81100262753">Dr. Prof. Schlesinger</a>&#39;s lectures.</p><h3>The Problem</h3><p>Given two training sets, X ⊂ ℝⁿ and Y ⊂ ℝⁿ, we want to find such positive number θ, vector μ, and positive-definite matrix Σ and that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FwbGWkz6BPsezNQskizy7x2&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FwbGWkz6BPsezNQskizy7x2&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="205" height="233" frameborder="0" scrolling="no"><a href="https://medium.com/media/99db3158836ba299821205d514654a42/href">https://medium.com/media/99db3158836ba299821205d514654a42/href</a></iframe><p>where</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FbUPjTcHUG1AbN28rSvQrwZ&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FbUPjTcHUG1AbN28rSvQrwZ&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="570" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/0150976154cbd08e9f542a53250e1371/href">https://medium.com/media/0150976154cbd08e9f542a53250e1371/href</a></iframe><h4>Fetching Ellipse Formula</h4><p>The inequalities can be drastically simplified. The first step is eliminating all the values outside the exponent in the density of multivariate normal distribution (and moving them to θ). We can remove the expression in parentheses containing π because it is positive and does not affect the inequality sign. The less obvious thing is that we can remove the determinant, but it is possible because <a href="https://mathworld.wolfram.com/PositiveDefiniteMatrix.html">the determinant of a positive-definite matrix is always positive</a>. Getting rid of the exponent is more straightforward using natural logarithm.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FXPaBjcZPHaMFeCNfJBf3z&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FXPaBjcZPHaMFeCNfJBf3z&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="529" height="294" frameborder="0" scrolling="no"><a href="https://medium.com/media/29286f330d65ecff2207779c60ef28e6/href">https://medium.com/media/29286f330d65ecff2207779c60ef28e6/href</a></iframe><p>We can see that having a positive θ and positive-definite Σ is essential for this conversion. Now, I will move the minus from the left side to the right side. Be very careful with such modifications: the sign swap changes the inequality.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fedi2tYxpdP2iGemmvEYddz&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fedi2tYxpdP2iGemmvEYddz&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="550" height="176" frameborder="0" scrolling="no"><a href="https://medium.com/media/8ea431491d08df4c031fb532143ff0aa/href">https://medium.com/media/8ea431491d08df4c031fb532143ff0aa/href</a></iframe><p>By <a href="https://en.wikipedia.org/wiki/Definite_matrix#Definitions_for_real_matrices">the definition of positive definiteness of a matrix</a>, the left-hand side of the expression is positive for any x and μ. This means that non-positive values of the right-hand side are entirely useless, so we imply new constraints on θ:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FgzR1Y16mHG9nzD7qk9UdHV&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FgzR1Y16mHG9nzD7qk9UdHV&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="564" height="139" frameborder="0" scrolling="no"><a href="https://medium.com/media/4adc690a9ebb7c1df695480f5aab03f7/href">https://medium.com/media/4adc690a9ebb7c1df695480f5aab03f7/href</a></iframe><p>Considering the last conclusion, I introduce a new positive-definite matrix A to simplify the inequalities:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FxtQhtxZ4boL8ZAAsebSUAm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FxtQhtxZ4boL8ZAAsebSUAm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="319" height="159" frameborder="0" scrolling="no"><a href="https://medium.com/media/03f5827c5f04185b5d9c43b946ae9756/href">https://medium.com/media/03f5827c5f04185b5d9c43b946ae9756/href</a></iframe><p>Now, we have a new classification problem equivalent to the initial one, but looking way more straightforward. Given two training sets, X ⊂ ℝⁿ and Y ⊂ ℝⁿ, we want to find such positive vector μ and positive-definite matrix A that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FazESUkgwUbXYtXNMximEfm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FazESUkgwUbXYtXNMximEfm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="300" height="213" frameborder="0" scrolling="no"><a href="https://medium.com/media/614061eaf5dbebfe56883f2c60ea56eb/href">https://medium.com/media/614061eaf5dbebfe56883f2c60ea56eb/href</a></iframe><p>The left-hand side of the inequalities is <a href="https://en.wikipedia.org/wiki/Ellipsoid#As_a_quadric">the equation of an n-dimensional ellipsoid centred at </a>μ. Now, the sign change and matrix replacement make geometric sense. The logic behind this sign change is that being in a higher probability density region means being inside an ellipsoid defined by the multivariate normal distribution. Multiplication of the covariance matrix by a positive constant changes the variances of the random vectors’ components, thus modifying the region where the probability density does not reach a specific value.</p><p>During the problem simplification, we dropped θ, thus reducing the number of degrees of freedom, did we not? Are we still working on the initial task at its entire complexity? The task was to build a classifier based on two sets of vectors separated by inequalities containing a multivariate normal distribution and a threshold θ. During the simplification, we discovered that the threshold is bound with the covariance matrix Σ: we can increase the variances and the threshold in a determined way without altering any inequality. Therefore, the problem did not have this additional degree of freedom, and we eliminated the redundant member.</p><h4>Problem Linearisation</h4><p>The problem does not look linear, which implies the necessity of modifying the algorithm without sacrificing its convergence guarantee for separable sets. Let me remind you that we can solve the problem of finding such vector α that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fpjk7v9AJWAQzCZ7Gm7eSz1&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fpjk7v9AJWAQzCZ7Gm7eSz1&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="185" frameborder="0" scrolling="no"><a href="https://medium.com/media/0dd536cb01b20d7c1c114173f9024715/href">https://medium.com/media/0dd536cb01b20d7c1c114173f9024715/href</a></iframe><p>Now, we want to find such vector μ and positive-definite matrix A that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FazESUkgwUbXYtXNMximEfm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FazESUkgwUbXYtXNMximEfm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="300" height="213" frameborder="0" scrolling="no"><a href="https://medium.com/media/614061eaf5dbebfe56883f2c60ea56eb/href">https://medium.com/media/614061eaf5dbebfe56883f2c60ea56eb/href</a></iframe><p>Let us expand the quadratic form to manage the problem more easily:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FeCkgUQJfjS1WcrfUm8HiBX&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FeCkgUQJfjS1WcrfUm8HiBX&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="577" height="138" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fb2ce5de38b385d1987bf7ec6cc8a37/href">https://medium.com/media/1fb2ce5de38b385d1987bf7ec6cc8a37/href</a></iframe><p>I want to represent the right-side quadratic form as a scalar product of a vector that depends on the input and a vector that depends on the matrix. Let me do it step by step. Look at the following expression:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F3Fqmmc3VHPLEZeVpz5kYxY&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F3Fqmmc3VHPLEZeVpz5kYxY&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="485" height="171" frameborder="0" scrolling="no"><a href="https://medium.com/media/909a7baaaa37f243954b3efbcad277a6/href">https://medium.com/media/909a7baaaa37f243954b3efbcad277a6/href</a></iframe><p>I represented a quadratic form as a sum of dot products. The next thing to do is to concatenate the vectors to get an ordinary dot product:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FmtxcXXYwGSHhmZCgivLbyt&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FmtxcXXYwGSHhmZCgivLbyt&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="470" height="193" frameborder="0" scrolling="no"><a href="https://medium.com/media/dfb0164f07314daac5162f3983730927/href">https://medium.com/media/dfb0164f07314daac5162f3983730927/href</a></iframe><p>Finally, we have got the expression that contains only dot products of vectors</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FnvaWqqNvQS5Pjf5nHRaV5m&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FnvaWqqNvQS5Pjf5nHRaV5m&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="960" height="144" frameborder="0" scrolling="no"><a href="https://medium.com/media/7606a2d31ceb2542221dc9cb18b0ac51/href">https://medium.com/media/7606a2d31ceb2542221dc9cb18b0ac51/href</a></iframe><p>Now, let us return to the inequality. We can subtract one from both sides of the inequalities to have zero on the right side to make it look more like the task for the linear classifier:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fhw9hDn1QeN8p2sXY1adPAr&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fhw9hDn1QeN8p2sXY1adPAr&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="542" height="187" frameborder="0" scrolling="no"><a href="https://medium.com/media/d520983a95ca0a217f7dbfc9d084e457/href">https://medium.com/media/d520983a95ca0a217f7dbfc9d084e457/href</a></iframe><p>The last puzzle piece is the conversion that reveals the dot product in this expression:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FwKz1S1cQfaSJwDU4hzH2Wt&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FwKz1S1cQfaSJwDU4hzH2Wt&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="542" height="235" frameborder="0" scrolling="no"><a href="https://medium.com/media/7486444add18b701eee8e875b837c54d/href">https://medium.com/media/7486444add18b701eee8e875b837c54d/href</a></iframe><p>We have a problem that the perceptron algorithm can solve, which is still not equal to the initial task. Given two datasets, X and Y, find such vector α that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F4w4mfUTigSvYjRpd5jRosz&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F4w4mfUTigSvYjRpd5jRosz&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="333" height="354" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae9dc747e94bf6888c3551fe5097432c/href">https://medium.com/media/ae9dc747e94bf6888c3551fe5097432c/href</a></iframe><h4>Matrix Eigendecomposition</h4><p>The output matrix must be <a href="https://en.wikipedia.org/wiki/Definite_matrix">positive-definite</a>. This means that any quadratic form determined by this matrix must be positive if the argument is a non-zero vector:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fju2t3r8zA1uXFjs4VRWCUk&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fju2t3r8zA1uXFjs4VRWCUk&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="349" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/65f812a8d11d5accdacf0d1a7896d188/href">https://medium.com/media/65f812a8d11d5accdacf0d1a7896d188/href</a></iframe><p>We know how to linearise the input, but checking every vector is infeasible for this algorithm. There is another equivalent definition of positive definiteness: the matrix must be symmetric, and all <a href="https://en.wikipedia.org/wiki/Eigenvalue">eigenvalues</a> must be positive. In turn, an eigenvalue is the scale factor for the corresponding eigenvector multiplied by the matrix:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FmnFcXrvqoSkNmjkJ1cDYC4&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FmnFcXrvqoSkNmjkJ1cDYC4&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/938a017f4d19e9ae5f0e66576d60df79/href">https://medium.com/media/938a017f4d19e9ae5f0e66576d60df79/href</a></iframe><p>Multiplication of both sides by the eigenvector gives us</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fod7jGNm5Pq8qZuUgzYcqCV&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fod7jGNm5Pq8qZuUgzYcqCV&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="554" height="138" frameborder="0" scrolling="no"><a href="https://medium.com/media/eca0a1e34133a8b808185ca324cf7b59/href">https://medium.com/media/eca0a1e34133a8b808185ca324cf7b59/href</a></iframe><p>Here, we can see that a sign of an eigenvalue induces the same sign of the corresponding quadratic form:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FtBTQ7V6qvtfQuYQ9WPogC&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FtBTQ7V6qvtfQuYQ9WPogC&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="433" height="172" frameborder="0" scrolling="no"><a href="https://medium.com/media/511e277b5d7181227d88420d6f358aa8/href">https://medium.com/media/511e277b5d7181227d88420d6f358aa8/href</a></iframe><p>Thus, if all eigenvalues are positive, the matrix is positive-definite by definition. If any eigenvalue is not positive, we should add the corresponding eigenvector to the training set. However, we should transform it right:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FbuPHfy5xrdRdCLXMG8bYm1&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FbuPHfy5xrdRdCLXMG8bYm1&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/8c2a1fdd0bdeba6def9dd24f08b70078/href">https://medium.com/media/8c2a1fdd0bdeba6def9dd24f08b70078/href</a></iframe><h4>Consistency</h4><p>According to our conversions, the last element of the vector α corresponds to</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fo1wEtuRWS8FSQxSDyKmd8o&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fo1wEtuRWS8FSQxSDyKmd8o&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/6329fa4aeb20614e485daefa28449b58/href">https://medium.com/media/6329fa4aeb20614e485daefa28449b58/href</a></iframe><p>We assume</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F5FrhKG1VTitGxHSfVJnqQe&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F5FrhKG1VTitGxHSfVJnqQe&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="960" height="112" frameborder="0" scrolling="no"><a href="https://medium.com/media/5b754e8fa512e06dba59ae78552da1da/href">https://medium.com/media/5b754e8fa512e06dba59ae78552da1da/href</a></iframe><p>We want to eliminate this constant. Note that, at this point, vector α cannot be zero. This means we do not have to consider the case when constant c is zero.</p><p>We can fetch cA and μ from α. We know that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F9iZSiHU8Pf9WkNwcPjyqqN&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F9iZSiHU8Pf9WkNwcPjyqqN&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="462" height="96" frameborder="0" scrolling="no"><a href="https://medium.com/media/d5f07d0d92728d6e1ec5e57fd95aa809/href">https://medium.com/media/d5f07d0d92728d6e1ec5e57fd95aa809/href</a></iframe><p>We can easily compute the constant:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FnEm3jpHfWKAuxGMhfXXVE4&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FnEm3jpHfWKAuxGMhfXXVE4&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="241" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/4ffa54b9d99ca65c9839925ddfef3c9e/href">https://medium.com/media/4ffa54b9d99ca65c9839925ddfef3c9e/href</a></iframe><p>Note that the matrix multiplied by the constant is what we already have in vector α, so it is a known variable. Next, divide the vector by the constant if it is non-zero.</p><h3>The Algorithm</h3><p>We are ready to compile the algorithm to train a binary classifier for multivariate normal distribution.</p><h4><strong>Initialisation</strong></h4><p>Given two training sets, X ⊂ ℝⁿ and Y ⊂ ℝⁿ, we initialise a vector</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FmD4FTf8J2WoSDToc7VM7xw&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FmD4FTf8J2WoSDToc7VM7xw&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="246" height="177" frameborder="0" scrolling="no"><a href="https://medium.com/media/68b6c7029586be74ff91a475f37ed2e3/href">https://medium.com/media/68b6c7029586be74ff91a475f37ed2e3/href</a></iframe><p>Note that -1 in the end is required to make the solution consistent from the very beginning. Of course, a zero matrix is not suitable, but it can be an argument for the transformation function. Nevertheless, a zero vector cannot be an output of the transformation function.</p><h4><strong>Training</strong></h4><p>We define a training set transformation</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FsfvrrM9YY2qWRJpv9hRbxp&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FsfvrrM9YY2qWRJpv9hRbxp&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="333" height="160" frameborder="0" scrolling="no"><a href="https://medium.com/media/dae3e9251a27c3c0feba4e2d02eb1a55/href">https://medium.com/media/dae3e9251a27c3c0feba4e2d02eb1a55/href</a></iframe><p>The update rules are almost the same as for an ordinary algorithm: if a vector from X is misclassified, subtract it from α; if a vector from Y is misclassified, add it to α:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F6qJncwaK2rgLjWiif3PcJ6&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F6qJncwaK2rgLjWiif3PcJ6&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="367" height="164" frameborder="0" scrolling="no"><a href="https://medium.com/media/547ab12dc447854d04689fed917e7ee0/href">https://medium.com/media/547ab12dc447854d04689fed917e7ee0/href</a></iframe><p>If the update is needed, check the vectors from X and Y again. If they all fit inequalities</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FgYfQeaD9F6EwfEQEJzfWWn&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FgYfQeaD9F6EwfEQEJzfWWn&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="370" height="164" frameborder="0" scrolling="no"><a href="https://medium.com/media/f50737cb59d6b801614545faf1a2df55/href">https://medium.com/media/f50737cb59d6b801614545faf1a2df55/href</a></iframe><p>go to the next step — ensuring positive definiteness.</p><h4>Ensuring Positive Definiteness</h4><p>We need to check the eigenvalues of matrix A. Considering the equation</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fx6fiXoYA8J341GZ2ecbg55&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fx6fiXoYA8J341GZ2ecbg55&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="542" height="161" frameborder="0" scrolling="no"><a href="https://medium.com/media/e71ef357f13efb8fc508f41c1957b159/href">https://medium.com/media/e71ef357f13efb8fc508f41c1957b159/href</a></iframe><p>we can easily fetch the matrix from the vector α. Do not worry about confusing columns and rows of the matrix: the algorithm is structured so that the matrix is symmetric. The formula simplifies to</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FbHoS8RaNy48Gc5xqZHA34Y&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FbHoS8RaNy48Gc5xqZHA34Y&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="542" height="161" frameborder="0" scrolling="no"><a href="https://medium.com/media/51779f79a76b305738f5a5723ec93eb5/href">https://medium.com/media/51779f79a76b305738f5a5723ec93eb5/href</a></iframe><p>Find all eigenvalues; this can be done by libraries such as <a href="https://numpy.org/doc/stable/reference/generated/numpy.linalg.eig.html">NumPy</a> or <a href="https://eigen.tuxfamily.org/dox/classEigen_1_1EigenSolver.html">Eigen</a> or languages such as <a href="https://cran.r-project.org/web/packages/matlib/vignettes/eigen-ex1.html">R</a> or <a href="https://www.mathworks.com/help/matlab/ref/eig.html">MATLAB</a>. If any of them is not positive, take the corresponding eigenvector and make the update:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FtYC28cmJT21jA9vntP7G7i&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FtYC28cmJT21jA9vntP7G7i&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="330" height="176" frameborder="0" scrolling="no"><a href="https://medium.com/media/72a5d4527e85755074ceef1de52dc2c4/href">https://medium.com/media/72a5d4527e85755074ceef1de52dc2c4/href</a></iframe><p>If no updates are required, go to the next step. If any updates are needed, perform them and return to the previous step.</p><h4>Ensuring Consistency</h4><p>Divide the vector by the constant to ensure the consistency of the vector with the problem:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjahzH4CYUFcCtci31dAj8r&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FjahzH4CYUFcCtci31dAj8r&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="351" height="176" frameborder="0" scrolling="no"><a href="https://medium.com/media/92cf56a85fcf28811a941f3fd1357f24/href">https://medium.com/media/92cf56a85fcf28811a941f3fd1357f24/href</a></iframe><p>If c is less than zero, return to the first training step. If c is greater than zero, the classification results are not changed, so the training is finished. I do not know what to do if the constant is zero, so I leave it as a task for you.</p><h3>Conclusions and Further Directions</h3><p>For those who got here, look at the animation of the learning process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/388/1*gq-J6_RI8yoR4b_aW3-qnQ.gif" /><figcaption>Training a classifier for finding a bounding ellipse. Animation by the Author.</figcaption></figure><p>This story unfolds the perceptron algorithm, as you may not have known it before. Feature space linearisation (or warping) is a widely used trick (an analogue to the kernel trick). However, ensuring such non-trivial properties as positive definiteness was eye-opening.</p><p>The beauty of this algorithm is that it can produce correct results with an empty X, empty Y, or when training sets are not provided.</p><p>This path was not easy, but I still have tasks for you:</p><ul><li>Prove that this algorithm converges as well if a solution exists.</li><li>Prove that the resulting matrix is symmetric.</li><li>Find the way to fetch μ.</li><li>Shrink the vector α by exploiting the matrix symmetry.</li><li>Implement a code for arbitrary dimensions (and think about visualisation).</li><li>Play with other possible steps of training (checking eigenvalues before training, continuing training only after ensuring positive definiteness of the matrix, etc.).</li><li>Think about the consistency insurance step. What should we do if the constant is zero?</li><li>Can you find any references to this algorithm?</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a05029c2629d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Perceptron. Part 1: The Story Retold]]></title>
            <link>https://medium.com/@valeriy.krygin/perceptron-part-1-the-story-retold-2065c341b60d?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/2065c341b60d</guid>
            <category><![CDATA[math]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[perceptron]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Tue, 01 Oct 2024 10:41:49 GMT</pubDate>
            <atom:updated>2024-11-01T11:51:12.905Z</atom:updated>
            <content:encoded><![CDATA[<h4>The basics of solving systems of strict linear inequalities</h4><p>Stories of the series:</p><ul><li><a href="https://medium.com/@valeriy.krygin/perceptron-part-1-the-story-retold-2065c341b60d">Perceptron. Part 1: The Story Retold</a></li><li><a href="https://medium.com/@valeriy.krygin/perceptron-part-2-the-story-untold-a05029c2629d">Perceptron. Part 2: The Story Untold</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f1Z-5ZbydxL3wqVZ0nf8vA.png" /><figcaption>Binary classification. Picture by the Author.</figcaption></figure><h3>Table of Contents</h3><ul><li><a href="#649f">Binary Classification</a><br>- <a href="#37b5">The Classification Algorithm</a><br>- <a href="#d911">The Learning Algorithm</a><br>- <a href="#a9d9">The Learning Algorithm Convergence</a></li><li><a href="#e96d">Multiclass Classification</a><br>- <a href="#325f">The Problem</a><br>- <a href="#59dc">Reduction to The Binary Classification Problem</a><br>- <a href="#a3f4">The Learning Algorithm Inference</a><br>- <a href="#c49a">Multiclass Classification</a></li><li><a href="#0346">Conclusions and Further Directions</a></li></ul><h3>Introduction</h3><p>Perceptron itself is an algorithm that does not need an introduction. However, some of its applications are so unknown that I plan to dedicate multiple stories to them. The first story contains the basics so that you can follow my subsequent writings.</p><h3>Binary Classification</h3><p>Let me begin with the basics of solving systems of strict linear inequalities using perceptron.</p><h4>The Classification Algorithm</h4><p>Given a constant vector α ∈ ℝⁿ, a linear classifier is defined for any x ∈ ℝⁿ as follows:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FgAnKNnABMwEXqH7U1N64dy&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FgAnKNnABMwEXqH7U1N64dy&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="170" frameborder="0" scrolling="no"><a href="https://medium.com/media/61daf5a7dd24dc45a9488b9052ac06c1/href">https://medium.com/media/61daf5a7dd24dc45a9488b9052ac06c1/href</a></iframe><p>A bias bit is frequently added to the classifier by default. I will show you its extended possibilities soon.</p><h4>The Learning Algorithm</h4><p>Given a non-empty training set X ⊂ ℝⁿ, we want to find such vector α ∈ ℝⁿ that classifies the training set right:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FqvD9n1nng36Msid6vPCjQE&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FqvD9n1nng36Msid6vPCjQE&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/7b5d034cb211e371b3580eef2d2d4a8d/href">https://medium.com/media/7b5d034cb211e371b3580eef2d2d4a8d/href</a></iframe><p>The algorithm consists of a few simple steps:</p><ol><li>Initialise i ← 0 and αᵢ = 0.</li><li>Repeat until convergence</li></ol><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FuWA6qkKSrgWxF7kZvs9TWT&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FuWA6qkKSrgWxF7kZvs9TWT&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="348" height="170" frameborder="0" scrolling="no"><a href="https://medium.com/media/6f2ce1b175a232e9bf6db67a566e3bd7/href">https://medium.com/media/6f2ce1b175a232e9bf6db67a566e3bd7/href</a></iframe><p>The result is α = αᵢ.</p><p>You may have seen variations involving learning rate, another stop criteria, and having two explicit datasets for two classes. I chose this one to keep the story simple yet correct.</p><h4>The Learning Algorithm Convergence</h4><p>The learning algorithm converges for a non-empty training set X ⊂ ℝⁿ if such α exists that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FqvD9n1nng36Msid6vPCjQE&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FqvD9n1nng36Msid6vPCjQE&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/7b5d034cb211e371b3580eef2d2d4a8d/href">https://medium.com/media/7b5d034cb211e371b3580eef2d2d4a8d/href</a></iframe><p>This proof follows the ideas described in “<a href="https://cs.uwaterloo.ca/~y328yu/classics/novikoff.pdf">On Convergence Proofs for Perceptrons</a>” by A. Novokoff (1962).</p><p><strong>A Lower Bound</strong></p><p>It is evident from the scalar product properties that any vector&#39;s projection onto another is not longer than any of the participating vectors. In the context of the proof, it means that for any iteration i + 1</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FwaPviVJjrteut72v9MCpvm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FwaPviVJjrteut72v9MCpvm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="436" height="152" frameborder="0" scrolling="no"><a href="https://medium.com/media/3067a398aa2a78c35b10e71e9f0b8a07/href">https://medium.com/media/3067a398aa2a78c35b10e71e9f0b8a07/href</a></iframe><p>If there is an iteration i + 1, such vector x exists that was misclassified with vector αᵢ. Thus,</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjrKrD1qdwzDVxMsmFRK8RF&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FjrKrD1qdwzDVxMsmFRK8RF&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="495" height="152" frameborder="0" scrolling="no"><a href="https://medium.com/media/dc2c8cc97d06bb4c21155360ff78091e/href">https://medium.com/media/dc2c8cc97d06bb4c21155360ff78091e/href</a></iframe><p>Given a finite training set X (to ensure the existence of minimum),</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FwqgSU1oRfqTR6u9yzJoidr&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FwqgSU1oRfqTR6u9yzJoidr&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="414" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/a56655200f801d6e701ab7b0a144abeb/href">https://medium.com/media/a56655200f801d6e701ab7b0a144abeb/href</a></iframe><p>Bearing in mind α₀ = 0, the recursive expansion of these inequalities leads to a lower bound</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FidiFhStLrCcjz8fZdtZtnF&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FidiFhStLrCcjz8fZdtZtnF&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="502" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/824bf38b6aefb90ac9ce0e41c1d9df1f/href">https://medium.com/media/824bf38b6aefb90ac9ce0e41c1d9df1f/href</a></iframe><p><strong>An Upper Bound</strong></p><p>Again, consider the iteration number i + 1. If we have come so far, we required a correction on step i because vector x was misclassified, implying</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FwMG3DRN1tYRVyG7mudUnpR&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FwMG3DRN1tYRVyG7mudUnpR&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="704" height="96" frameborder="0" scrolling="no"><a href="https://medium.com/media/9bf89621d98fd08fa399bf36a40ecc27/href">https://medium.com/media/9bf89621d98fd08fa399bf36a40ecc27/href</a></iframe><p>Given a finite training set X (to ensure the existence of maximum),</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FfTNq7U6XXiZ9JMu4kDpa2Q&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FfTNq7U6XXiZ9JMu4kDpa2Q&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="568" height="146" frameborder="0" scrolling="no"><a href="https://medium.com/media/64671ab0fa6e5416766cbbbb896e7ab5/href">https://medium.com/media/64671ab0fa6e5416766cbbbb896e7ab5/href</a></iframe><p>Because of the initialisation α₀ = 0, we can expand this inequality recursively to get an upper bound</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F2DopcCEjCjaTqgtqCcV75x&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F2DopcCEjCjaTqgtqCcV75x&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="616" height="146" frameborder="0" scrolling="no"><a href="https://medium.com/media/16e1b1bce5defb3016715ab70e2f5a37/href">https://medium.com/media/16e1b1bce5defb3016715ab70e2f5a37/href</a></iframe><p><strong>The Proof of Convergence</strong></p><p>For simplicity, let me introduce two aliases:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FaL5at1VgQhPVe2oVNhEh8A&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FaL5at1VgQhPVe2oVNhEh8A&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="158" frameborder="0" scrolling="no"><a href="https://medium.com/media/3f20509c8d179bbcd5fbdc89e1b84662/href">https://medium.com/media/3f20509c8d179bbcd5fbdc89e1b84662/href</a></iframe><p>The meaning of D is simple: it is the norm of the longest vector from the training set. The meaning of d is more shady, so let me explain it. Vector α divided by its norm is a unit vector that defines a hyperplane containing the coordinate system origin and having a normal vector α. The dot product of the unit normal vector with a vector x is the distance from the vector x to the plane. This means that d is the distance from the plane to the closest vector from the training set.</p><p>We have a system of two inequalities that can be flattened into a chain:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FmwUYMxKz6oa2fMY1bP4yEj&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FmwUYMxKz6oa2fMY1bP4yEj&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="401" height="172" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb10ce1df09427a57069e545e1c7f6fe/href">https://medium.com/media/fb10ce1df09427a57069e545e1c7f6fe/href</a></iframe><p>This gives us an upper bound for the number of required iterations</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F5QFRUJixryyXJeuTeSz1E6&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F5QFRUJixryyXJeuTeSz1E6&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="482" height="96" frameborder="0" scrolling="no"><a href="https://medium.com/media/0485302930980289b61173e65ab246ba/href">https://medium.com/media/0485302930980289b61173e65ab246ba/href</a></iframe><p><strong>Comments</strong></p><p>Note that the last iteration is not i but i + 1, so the upper bound of the total iterations required is</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FnrRCYZnfCB3fmunxbWyrYt&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FnrRCYZnfCB3fmunxbWyrYt&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="159" frameborder="0" scrolling="no"><a href="https://medium.com/media/c651de4dcfd0799045df9647ac2edbd2/href">https://medium.com/media/c651de4dcfd0799045df9647ac2edbd2/href</a></iframe><p>The intuitive part of the result: the larger the ratio between the vectors’ norm and their distance from a separating hyperplane — the more iterations are required to reach the result. Thus, if the slack is tiny, the algorithm requires working harder to achieve it than when closing a large gap, and if the gap is zero (there is no separating plane), the algorithm does not converge. The counterintuitive part of the result is that the number of iterations does not depend on the number of elements in the training set. Thus, asymptotically, it requires a linear number of calculations of scalar products and sums; the problem is that the constant grows quadratically with the ratio between the maximum vector size and the gap between a separating plane and the training set.</p><p>If the training <a href="https://en.wikipedia.org/wiki/Open_set">set is open</a>, we can use <a href="https://en.wikipedia.org/wiki/Infimum_and_supremum">infimum and supremum</a> instead of <a href="https://en.wikipedia.org/wiki/Maximum_and_minimum">maximum and minimum</a> correspondingly. If it is infinite and <a href="https://en.wikipedia.org/wiki/Closed_set#:~:text=In%20a%20topological%20space%2C%20a,confused%20with%20a%20closed%20manifold.">closed</a>, we can still use maximum. Also, we can consider only the subset used during the corrections, which is always finite if the solution exists.</p><h3>Multiclass Classification</h3><p>This section follows the lectures of Dr. Prof. Schlesinger and can be found in the book “<a href="https://doi.org/10.1007/978-94-017-3217-8">Ten Lectures on Statistical and Structural Pattern Recognition</a>” by Michail I. Schlesinger and Václav Hlaváč (2002).</p><h4>The Problem</h4><p>Given m finite training sets</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F65D4JvJgLbYbuP5PuPgGTG&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F65D4JvJgLbYbuP5PuPgGTG&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="275" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/2f7aafc91e4e44dccb813d3b59b85bf1/href">https://medium.com/media/2f7aafc91e4e44dccb813d3b59b85bf1/href</a></iframe><p>we want to find such vectors</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F4zYMr2PJ8mgpb6WYqt1FGF&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F4zYMr2PJ8mgpb6WYqt1FGF&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="263" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/9a56771fdb25261e384026deab95658b/href">https://medium.com/media/9a56771fdb25261e384026deab95658b/href</a></iframe><p>that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FpuCEJGJ6RTdZXJruRY4mdK&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FpuCEJGJ6RTdZXJruRY4mdK&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="406" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/27c0241c11f8bab60445fb3aa42abc67/href">https://medium.com/media/27c0241c11f8bab60445fb3aa42abc67/href</a></iframe><p>Note that i is not a number of an iteration but an index of a vector.</p><h4>Reduction to The Binary Classification Problem</h4><p>Surprisingly, this problem is equivalent to the previous one. First, let me concatenate the vectors into a single one:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FsYCyKrvLmWwJiwy6Y3Xf&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FsYCyKrvLmWwJiwy6Y3Xf&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="541" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/28532443b7e50f42f8b5a9303fc9dc6d/href">https://medium.com/media/28532443b7e50f42f8b5a9303fc9dc6d/href</a></iframe><p>Next, we must produce a new training set X consisting of nm-dimensional vectors:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FiDhpXEJ2GfXrvUXzHLb6xD&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FiDhpXEJ2GfXrvUXzHLb6xD&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="650" height="281" frameborder="0" scrolling="no"><a href="https://medium.com/media/46f0946f97a6c53fe32db5d8552c3b0b/href">https://medium.com/media/46f0946f97a6c53fe32db5d8552c3b0b/href</a></iframe><p>A careful look at this set reveals that the dot product of these vectors with α has a one-to-one correspondence with the differences from the original problem.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FgFxyZCDDhc18DGmYkYPjYN&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FgFxyZCDDhc18DGmYkYPjYN&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="613" height="257" frameborder="0" scrolling="no"><a href="https://medium.com/media/4d82241998854e411ddae1d621037d20/href">https://medium.com/media/4d82241998854e411ddae1d621037d20/href</a></iframe><p>Thus, we want to find such vector α that</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjPAgZmYnsquoRHuSbn3X4T&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FjPAgZmYnsquoRHuSbn3X4T&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="361" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/b13b02c2f64be7f6d3e4677e0c4eacad/href">https://medium.com/media/b13b02c2f64be7f6d3e4677e0c4eacad/href</a></iframe><h4>The Learning Algorithm Inference</h4><p>Let us increase the computational feasibility of the learning algorithm without losing its properties. Suppose we have an α, and there exist such i and j that i &gt; j and</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F7iyr2aMKXpF2PhRUAQNKjC&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F7iyr2aMKXpF2PhRUAQNKjC&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="502" height="184" frameborder="0" scrolling="no"><a href="https://medium.com/media/8797b493c11aecd8e2fe4684106b8fa3/href">https://medium.com/media/8797b493c11aecd8e2fe4684106b8fa3/href</a></iframe><p>or i &lt; j and</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FviyhMdn66PTcMn9aScwqCm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FviyhMdn66PTcMn9aScwqCm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="502" height="184" frameborder="0" scrolling="no"><a href="https://medium.com/media/27e58f4a097dc55cf40cb2d79c26facd/href">https://medium.com/media/27e58f4a097dc55cf40cb2d79c26facd/href</a></iframe><p>which means</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F4oXxLPEqmBWPTgL3bkpE91&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F4oXxLPEqmBWPTgL3bkpE91&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/d8ace36a2bd1e33ad7b0011c7da3b0e8/href">https://medium.com/media/d8ace36a2bd1e33ad7b0011c7da3b0e8/href</a></iframe><p>in terms of the initial problem.</p><p>In this case, we need to add the misclassified vector to α. This means that we add x to the part of α that corresponds to αᵢ of the initial problem and subtract x from the part that corresponds to αⱼ. Thus, we have a simplified algorithm:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F5E8z21LQqc9L3VYP47zCH6&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F5E8z21LQqc9L3VYP47zCH6&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="307" height="170" frameborder="0" scrolling="no"><a href="https://medium.com/media/fc3757745dba83e5dd8a13001fecefe3/href">https://medium.com/media/fc3757745dba83e5dd8a13001fecefe3/href</a></iframe><h4>Multiclass Classification</h4><p>Let us summarise the knowledge. We have m finite training sets</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F2Ych7MZpPeQqp72ZZYaAX1&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F2Ych7MZpPeQqp72ZZYaAX1&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="275" height="136" frameborder="0" scrolling="no"><a href="https://medium.com/media/972f6a45c8062eed929b2bd26c44198c/href">https://medium.com/media/972f6a45c8062eed929b2bd26c44198c/href</a></iframe><p>The learning procedure is as follows:</p><ol><li>Initialise α₁, …, aₘ with n-dimensional zero vectors.</li><li>Repeat until convergence:</li></ol><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FiFvJ1AvGJ7aesd5JEA9Zfn&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FiFvJ1AvGJ7aesd5JEA9Zfn&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="406" height="170" frameborder="0" scrolling="no"><a href="https://medium.com/media/03e7fbd265c89bbf387a158aba2c6d59/href">https://medium.com/media/03e7fbd265c89bbf387a158aba2c6d59/href</a></iframe><p>Using the classifier is relatively simple when the number of classes is small. Given trained vectors α₁, …, aₘ, a vector x is a part of class k if</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fj6sjqKKsNGMdup9yW7DVju&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fj6sjqKKsNGMdup9yW7DVju&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="145" frameborder="0" scrolling="no"><a href="https://medium.com/media/bae1671b2252c2179109e2aff4c581ae/href">https://medium.com/media/bae1671b2252c2179109e2aff4c581ae/href</a></iframe><p>If multiple classes correspond to the equation, the solution depends on the problem to be solved. There are cases when you can choose any of the suitable classes.</p><h3>Conclusions and Further Directions</h3><p>The story is short and retold many times. However, for the following stories, I wanted to be precise in my definitions to not confuse readers who expect recommendations for choosing the learning rate, error rate estimates, validation set preparation, etc. In the following parts, I will reveal the things that are not spoken of frequently.</p><p>Here are the modifications of the learning and classification algorithms for you to think of (or look for in the book):</p><ol><li>Finding a separating plane not located at the origin of the coordinate system.</li><li>Finding a separating parabola.</li><li>Finding a separating circle.</li><li>Finding an optimal separating hyperplane.</li><li>Finding a separating ellipse (to reveal parameters of a Gaussian distribution).</li><li>Finding weights of vertices and/or edges for <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">dynamic programming on chains</a>.</li></ol><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2065c341b60d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Efficient Python Implementation of Scanline Stereo Vision]]></title>
            <link>https://medium.com/@valeriy.krygin/efficient-python-implementation-of-scanline-stereo-vision-c7dcff677b3c?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/c7dcff677b3c</guid>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[computer-vision]]></category>
            <category><![CDATA[numpy]]></category>
            <category><![CDATA[stereo-vision]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Sun, 01 Sep 2024 14:57:03 GMT</pubDate>
            <atom:updated>2024-09-02T17:06:12.944Z</atom:updated>
            <content:encoded><![CDATA[<h4>Python can be as fast as C++ in real-life Computer Vision problems</h4><p>This story describes a Python <a href="https://medium.com/@valeriy.krygin/scanline-stereo-vision-85ff252ec521">scanline stereo vision</a> implementation using <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">dynamic programming on chain graphs</a>. It aims to show some tips for efficiently implementing algorithms in Python — some are generic, and some are specific.</p><p>Source code: <a href="https://github.com/definability/python_scanline_stereo">definability/python_scanline_stereo</a>. I license the code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it.</p><p>It was compared with my C++ implementation of the same algorithm available at <a href="https://github.com/definability/dynamic_programming_chain_cpp">definability/dynamic_programming_chain_cpp</a>. I license the C++ code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it. However, the code uses the <a href="https://cimg.eu/">CImg Library</a> licensed under the terms of the <a href="http://www.cecill.info/licences/Licence_CeCILL_V2-en.html">CeCILL</a>. When you use any part of its code or any code that uses it (any file in the examples directory), read the license text carefully and follow it strictly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DFAg9b4Voxa3AXlWwrhj9A.png" /><figcaption>The performance comparison. Chart by the Author.</figcaption></figure><h3>Table of Contents</h3><ul><li><a href="#0829">Introduction</a></li><li><a href="#1d1c">The Baseline Implementation</a><br>- <a href="#1a91">Resources Allocation</a><br>- <a href="#a8e9">The Implementation</a><br>- <a href="#255e">The Baseline Code Performance</a></li><li><a href="#f185">The NumPy-based implementation</a><br>- <a href="#5bae">Avoid Loops</a><br>- <a href="#7b30">Avoid Redundant Copies and Allocations</a><br>- <a href="#8bdf">Use newaxis</a><br>- <a href="#3fcb">Use axis</a><br>- <a href="#e1ab">Use in-place operators</a><br>- <a href="#b7a4">Computing the Disparity Map</a></li><li><a href="#8942">Performance Comparison</a></li><li><a href="#549c">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>This story has appeared mainly because people say, “Python is slow.” I started working on this story months ago but understood that it needs more explanation than I can fit in a single concise writing. That is why pages like <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">Dynamic Programming on Chain Graphs. Part 1: The Problem</a>, <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">Dynamic Programming on Chain Graphs. Part 2: The Solution</a>, and <a href="https://medium.com/@valeriy.krygin/scanline-stereo-vision-85ff252ec521">Scanline Stereo Vision</a> appeared. I strongly recommend you to read them first if you want to understand what was benchmarked and decide whether this is a fair comparison. Also, I invite you to meet <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">Dynamic Programming on Chain Graphs. Part 3: Preparing for Implementation</a> and <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">Dynamic Programming on Chain Graphs. Part 4: The Implementation</a> to learn more about the C++ code I use in the benchmarks.</p><p>Here, you will find several pieces of advice on effective <a href="https://numpy.org/">NumPy</a> use. I could not stand adding a few paragraphs about <a href="https://numba.pydata.org/">Numba</a> because I believe that my writing about the efficient use of Python cannot be complete without mentioning <a href="https://en.wikipedia.org/wiki/Just-in-time_compilation">JIT</a>.</p><h3>The Baseline Implementation</h3><p>I will use the <a href="https://pillow.readthedocs.io/en/stable/">Pillow</a> (PIL) library to work with pictures in this story. I use <a href="https://github.com/pyenv/pyenv">pyenv</a> to manage different Python interpreters (mainly <a href="https://pypy.org/">PyPy</a> and <a href="https://github.com/python/cpython">CPython</a>) and <a href="https://pipenv.pypa.io/en/latest/">pipenv</a> to control packages and virtual environments conveniently. I highly recommend that you also use virtual environments. There is a helpful environment variable, <a href="https://pip.pypa.io/en/stable/cli/pip/#cmdoption-require-virtualenv">PIP_REQUIRE_VIRTUALENV</a>, which enforces using of virtual environments.</p><p>Let me begin with the straightforward implementation of the <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e#2851">memory-efficient</a> algorithm. There are many simple ways to implement each algorithm step, but I chose the one that allows me to keep this story short and show the main ideas. Thus, I will use <a href="https://numpy.org/">numpy</a> straight away. Afraid not: I will explain some optimisations used in this baseline code. I will also skip the explanation of arguments parsing and input validation: you can find it on my <a href="https://github.com/definability/python_scanline_stereo">GitHub</a>, and it does not mean a lot from the performance perspective.</p><h4>Resources Allocation</h4><p>Given a pair of greyscale images of the same size, disparity levels count, and smoothness term, we want to solve the stereo vision problem.</p><p>The first optimisation here is to allocate all the arrays beforehand. Using <a href="https://docs.python.org/3/tutorial/datastructures.html#more-on-lists">list.append</a> may slow down your program; using <a href="https://numpy.org/doc/stable/reference/generated/numpy.append.html">numpy.append</a> may kill the performance — do not use it until you are sure it is the only right way to do this. Suppose you know only the upper boundary for the resulting array size, enough memory to store it, and enough time to allocate it. In that case, allocating the entire array and then deleting the rest is probably beneficial.</p><p>I specify the data types explicitly using the dtype argument. For example, <a href="https://numpy.org/doc/stable/reference/generated/numpy.empty.html">numpy.empty</a> creates a float array by default; we do not need it for the disparity map. Do not use <a href="https://numpy.org/doc/stable/reference/generated/numpy.empty.html">numpy.empty</a> unless you are sure you will fill the entire array and not rely on the temporary values for debugging.</p><pre><br>def solve_naive(<br>    *,<br>    left_image: ndarray,<br>    right_image: ndarray,<br>    max_disparity: int,<br>    edge_smoothness: float,<br>    use_numba=False,<br>) -&gt; ndarray:<br><br>    height, width = left_image.shape<br>    disparity_levels = min(max_disparity + 1, width - 1)<br>    edges = empty((disparity_levels, disparity_levels), dtype=&quot;float64&quot;)<br>    disparity_map = empty((height, width), dtype=&quot;int64&quot;)<br>    cache = full((height, width, disparity_levels), inf, dtype=&quot;float64&quot;)<br><br>    return implementation(<br>        cache,<br>        disparity_levels,<br>        disparity_map,<br>        edge_smoothness,<br>        edges,<br>        height,<br>        left_image,<br>        right_image,<br>        width,<br>    ).astype(&quot;uint8&quot;)</pre><h4>The Implementation</h4><p>Populate the edges. I use an array instead of computing these simple penalties on demand. The use of the array allows for a drastic performance increase. Read about <a href="https://en.wikipedia.org/wiki/Lookup_table">lookup tables</a> to know more. You can see that I use edges[d, d_prime] instead of edges[d][d_prime]. This is another performance tip: when you use the indexing operator, it returns a <a href="https://numpy.org/doc/stable/user/basics.copies.html">view</a> of the array, so using two indexing operators to <a href="https://numpy.org/doc/stable/user/basics.indexing.html#single-element-indexing">access a single element</a> or subarray causes the creation of a redundant view.</p><pre>for d in range(disparity_levels):<br>    for d_prime in range(disparity_levels):<br>        edges[d, d_prime] = edge_smoothness * (d != d_prime)</pre><p>Calculate the first column of the cache. The approach is straightforward and is simply a translation from Math to Python.</p><pre>x = width - 1<br>d = 0<br>for y in range(height):<br>    cache[y, x, d] = abs(<br>        float(right_image[y, x]) - float(left_image[y, x]))</pre><p>Here, you can see a peculiar version of a minimal element computation: I initialise the best value with infinity (the value larger than any possible finite number), traverse all the losses, and check whether I found a better one. Do not use 1E6 or any other number you consider “large enough” in this case unless you are utterly sure about what you are doing: such an approach is error-prone, imposes questions about the choice of the particular value, and introduces a new [<a href="https://en.wikipedia.org/wiki/Magic_number_(programming)#Unnamed_numerical_constants">magic</a>] constant. If you use a type that does not allow infinity, try using the maximum value (for example, <a href="https://en.cppreference.com/w/cpp/types/numeric_limits/max">std::numeric_limits&lt;T&gt;::max</a> in C++).</p><pre>for y in range(height):<br>    for x in range(width - 2, -1, -1):<br>        for d in range(min(disparity_levels, width - x)):<br>            best_result = inf<br>            for d_prime in range(disparity_levels):<br>                absolute_difference = abs(<br>                    float(left_image[y, x + d])<br>                    - float(right_image[y, x])<br>                )<br>                loss = (<br>                    absolute_difference<br>                    + edges[d, d_prime]<br>                    + cache[y, x + 1, d_prime]<br>                )<br>                if loss &lt; best_result:<br>                    best_result = loss<br>            cache[y, x, d] = best_result</pre><p>Now, it is time to find the disparities. It is simple with <a href="https://numpy.org/doc/stable/reference/generated/numpy.argmin.html">numpy.argmin</a>. Begin with the last column.</p><pre>x = 0<br>for y in range(height):<br>    disparity_map[y, x] = argmin(cache[y, x])</pre><p>For the other columns, I use a self-made argmin similar to what was done to find the minimal element. I did this to avoid creating another array and explaining what just happened. However, I will do this in the next section.</p><pre>for y in range(height):<br>    for x in range(1, width):<br>        minimal_penalty = inf<br>        for d in range(min(disparity_levels, width - x)):<br>            penalty = edges[disparity_map[y, x - 1], d] + cache[y, x, d]<br>            if penalty &lt; minimal_penalty:<br>                minimal_penalty = penalty<br>                disparity_map[y, x] = d</pre><p>That is it. Now, it is beneficial to normalise the disparity map’s values to match a greyscale image scale (from 0 to 255) and return.</p><pre>return disparity_map * 255 // (disparity_levels - 1)</pre><h4>The Baseline Code Performance</h4><p>This code turtles (or even snails) towards the solution, or does it not? The key to this story is that it is not the slow Python but the <a href="https://devguide.python.org/internals/exploring/">CPython</a> interpreter running it slowly. Do not confuse <a href="https://devguide.python.org/internals/exploring/">CPython</a> and <a href="https://cython.org/">Cython</a>: <a href="https://devguide.python.org/internals/exploring/">CPython</a> is the most popular Python interpreter, and if you did not know this, be sure you use it when you call python or python3 command, while <a href="https://cython.org/">Cython</a> is a compiler of the Python-like language called Cython. Of course, Python is a feature-reach language, and some features (<a href="https://docs.python.org/3/library/functions.html#setattr">setattr</a>, type checks, etc.) slow down the performance.<a href="https://en.wikipedia.org/wiki/Just-in-time_compilation">JIT</a> (just-in-time) compilers can fix the problem: they can analyse the code and compile it into a byte code or machine code, which can then be executed. We will talk about them later in this writing.</p><h3>The NumPy-based Implementation</h3><p>To use NumPy efficiently, you should spend much time reading its documentation. I suggest starting with <a href="https://numpy.org/doc/stable/user/basics.indexing.html">Indexing on ndarrays</a> to know the basics of this powerful tool. Then, after writing some programs, familiarise yourself with <a href="https://numpy.org/doc/stable/reference/ufuncs.html">Universal functions</a>, as they provide a generic way to perform a lot of optimisations across a wide range of NumPy functions. After a while, you will understand the NumPy philosophy better and better and will be able to distinguish non-optimal approaches to solving some problems and looking for good ones.</p><p>Let me show you some principles I applied to solve the scanline stereo vision problem.</p><h4>Avoid Loops</h4><p>The beginning is almost the same — initialise some arrays. However, the computation of the edge penalties already contains performance tricks. Instead of computing the edge penalties in a loop, I create a 2-dimensional array with the required penalties and put zeros in the diagonal cells using the dedicated NumPy functions.</p><pre>left_image = array(left_image, dtype=float)<br>right_image = array(right_image, dtype=float)<br><br>width = left_image.shape[1]<br>disparity_levels = min(max_disparity + 1, width - 1)<br>edges = full((disparity_levels, disparity_levels), edge_smoothness, dtype=float)<br>fill_diagonal(edges, 0)<br>disparity_map = empty(left_image.shape, dtype=int)<br>cache = full((*left_image.shape, disparity_levels), inf)</pre><h4>Avoid Redundant Copies and Allocations</h4><p>Filling the first column can be done without writing loops. It could be as simple as</p><pre>cache[:, -1, 0] = abs(left_image[:, 0] - right_image[:, x]) # Slow</pre><p>This code leverages <a href="https://numpy.org/doc/stable/user/basics.indexing.html#slicing-and-striding">slicing</a> to avoid loops. Of course, loops can exist in the underlying implementation, but they are usually implemented in C and are incredibly more efficient than Python loops performed by CPython.</p><p>Count the number of redundant intermediate arrays created in the above line of code. We calculate a difference between two arrays, and NumPy allocates a new array for this purpose. Next, it takes this array to calculate a new array of absolute values (which means two arrays). Then, the result is copied to cache. After this, two redundant arrays must be destroyed. Libraries exist that support <a href="https://en.wikipedia.org/wiki/Lazy_evaluation">lazy evaluation</a> to avoid such wasteful use of CPU in similar cases: for example, <a href="https://opencv.org/">OpenCV</a> (see <a href="https://docs.opencv.org/3.4/d1/d10/classcv_1_1MatExpr.html">cv::MatExpr</a>) and <a href="http://eigen.tuxfamily.org/">Eigen</a> (see <a href="https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html">Lazy Evaluation and Aliasing</a>). As far as I know, <a href="https://numpy.org/devdocs/release/2.0.0-notes.html">NumPy 2.0</a> does not support this. However, it has a lot of functions supporting out parameter that allows you to specify where to store the result. For example, you can use <a href="https://numpy.org/doc/stable/reference/generated/numpy.subtract.html">numpy.subtract</a> and <a href="https://numpy.org/doc/stable/reference/generated/numpy.absolute.html">numpy.absolute</a> to avoid redundant copies and allocations.</p><pre>x = width - 1<br>current_disparity = 0<br>subtract(<br>    left_image[:, x], right_image[:, x],<br>    out=cache[:, x, current_disparity],<br>)<br>absolute(<br>    cache[:, x, current_disparity],<br>    out=cache[:, x, current_disparity],<br>)</pre><h4>Use <a href="https://numpy.org/doc/stable/reference/constants.html#numpy.newaxis">newaxis</a></h4><p>Computing the cache for other columns is more complicated. The beginning may already look clear: it contains basic <a href="https://numpy.org/doc/stable/user/basics.indexing.html#slicing-and-striding">slicing</a> and already-known out parameter. However, it contains one more exciting item called <a href="https://numpy.org/doc/stable/user/basics.indexing.html#dimensional-indexing-tools">newaxis</a>. It is an alias for <a href="https://docs.python.org/3/c-api/none.html">None</a>, so you may have seen code that uses <a href="https://docs.python.org/3/c-api/none.html">None</a> instead. You may also prefer using <a href="https://numpy.org/doc/stable/reference/generated/numpy.expand_dims.html">numpy.expand_dims</a>, which is okay because it also creates a view instead of a new array. These approaches aim to create a new “fake” dimension to the array to make it compatible with arrays of higher dimensionality.</p><pre>for x in range(width - 2, -1, -1):<br>    current_disparity_levels = min(disparity_levels, width - x)<br>    add(<br>        cache[:, x + 1, :current_disparity_levels, newaxis],<br>        edges[newaxis, :current_disparity_levels, :current_disparity_levels],<br>        out=penalties_sum[:, :current_disparity_levels, :current_disparity_levels],<br>    )</pre><h4>Use axis</h4><p>Next, we want to find minimum values for each row. However, the <a href="https://numpy.org/doc/stable/reference/generated/numpy.minimum.html">numpy.min</a> function will return only a single number for a given array. Do not worry: it also has a handy parameter called axis. You can provide the index of the dimension that should “disappear” after the computation or a tuple of such indices. It also supports negative indices to count axes from the end. Remember that we do not want to allocate redundant memory and use out parameter here. Read more about them in describing the <a href="https://numpy.org/doc/stable/reference/ufuncs.html#optional-keyword-arguments">Optional keyword arguments</a> of <a href="https://numpy.org/doc/stable/reference/ufuncs.html">Universal functions</a>.</p><pre>penalties_sum[:, :current_disparity_levels, :current_disparity_levels].min(<br>    axis=-2,<br>    out=penalties_min[:, :current_disparity_levels],<br>)</pre><h4>Use In-place Operators</h4><p>The loop iteration&#39;s ending is almost the same as computing a single column. It also contains a performance tip: use in-place operators +=, -=, *=, and others.</p><pre>subtract(<br>    left_image[:, x:x + current_disparity_levels], right_image[:, x, newaxis],<br>    out=cache[:, x, :current_disparity_levels],<br>)<br>absolute(<br>    cache[:, x, :current_disparity_levels],<br>    out=cache[:, x, :current_disparity_levels],<br>)<br>cache[:, x, :current_disparity_levels] += penalties_min[:, :current_disparity_levels]</pre><h4>Computing the Disparity Map</h4><p>This step contains no new generic tips but shows everything discussed so far.</p><pre>x = 0<br>argmin(cache[:, x], axis=-1, out=disparity_map[:, x])<br>edges = full((left_image.shape[0], disparity_levels), inf, dtype=float)<br>for x in range(1, width):<br>    current_disparity_levels = min(disparity_levels, width - x)<br>    not_equal(<br>        disparity_map[:, x - 1, newaxis],<br>        disparities[newaxis, :current_disparity_levels],<br>        out=edges[:, :current_disparity_levels],<br>    )<br>    edges[:, :current_disparity_levels] *= edge_smoothness<br>    argmin(<br>        cache[:, x, :current_disparity_levels]<br>        + edges[:, :current_disparity_levels],<br>        axis=-1,<br>        out=disparity_map[:, x],<br>    )</pre><p>Let me write a non-efficient ending to keep it short.</p><pre>return (disparity_map * 255 // (disparity_levels - 1)).astype(uint8)</pre><h3>Performance Comparison</h3><p>I used six binocular pairs of images 1000x1000 from <a href="https://vision.middlebury.edu/stereo/data/">Middlebury Stereo Datasets</a> to compare the performance. I launched the programs with the maximum disparities of 10, 20, 30, 40, and 50 and averaged the timings for each disparity along the pairs.</p><p>You have already seen the plot at the beginning of this page. Impressive, right? The “fast” but memory-greedy algorithm implemented in C++ appeared to be slower than the “compact” version that requires more arithmetic operations. The striking thing is that even the Python implementation is faster than the “fast” algorithm implemented in C++. How is that possible?</p><p>The naive Python implementation launched with CPython was very slow—it required two minutes for eleven disparity levels, so I did not even include it in the benchmark. The NumPy implementation is a hundred times faster, which is incredible: for large disparities, it is only three times slower than the reference C++ code (and ten times slower for small ones). I described the NumPy code in detail so you understand why it runs so well. Still, what is this <a href="https://numba.pydata.org/">Numba</a> thing?</p><p><a href="https://numba.pydata.org/">Numba</a> is a JIT compiler for Python. It compiles Python code once it is reached (lazily). It has a lot of limitations: it supports a <a href="https://numba.readthedocs.io/en/stable/reference/pysupported.html">limited subset of Python</a> and a <a href="https://numba.readthedocs.io/en/stable/reference/numpysupported.html">limited subset of NumPy</a> features. Nevertheless, it is enough to write a lot of helpful code because it supports most trivial NumPy constructs and operations and optimises loops very well.</p><p>You can use <a href="https://numba.pydata.org/numba-doc/dev/reference/jit-compilation.html">Numba JIT as a decorator</a>. We should use several parameters to receive the most from the Numba benefits. A very helpful parameter is the function <a href="https://numba.pydata.org/numba-doc/dev/reference/types.html#signatures">signature</a>. Also, I use <a href="https://numba.pydata.org/numba-doc/dev/user/jit.html#cache">cache</a>, <a href="https://numba.pydata.org/numba-doc/dev/user/jit.html#nogil">nogil</a>, and <a href="https://numba.pydata.org/numba-doc/0.50.0/user/performance-tips.html#fastmath">fastmath</a>. Use <a href="https://numba.pydata.org/numba-doc/dev/user/jit.html#cache">cache</a> carefully: sometimes it does not reset, so you may edit your code, but use the old cached version; I suggest using it after your code is ready. The <a href="https://numba.pydata.org/numba-doc/0.50.0/user/performance-tips.html#fastmath">fastmath</a> parameter is also tricky, so use it wisely.</p><pre>@njit(<br>    int64[:, ::1](<br>        float64[:, :, ::1],<br>        int64,<br>        int64[:, ::1],<br>        float64,<br>        float64[:, ::1],<br>        int64,<br>        uint8[:, ::1],<br>        uint8[:, ::1],<br>        int64,<br>    ),<br>    cache=True,<br>    nogil=True,<br>    fastmath=True,<br>)<br>def implementation(<br>    cache: ndarray,<br>    disparity_levels: int,<br>    disparity_map: ndarray,<br>    edge_smoothness: float,<br>    edges: ndarray,<br>    height: int,<br>    left_image: ndarray,<br>    right_image: ndarray,<br>    width: int<br>) -&gt; ndarray:</pre><p>I implemented the code exactly like this to be compatible with Numba. It is not so trivial, so you can try modifying the code to check which features work and which do not.</p><h3>Conclusion and Further Directions</h3><p>Python is not a slow language—the standard interpreter is slow; however, some features of Python make implementing a fast generic interpreter very challenging. High-quality JIT and AOT compilers can elevate the performance of your code to a new level if you give up some flexibility. When your choice of interpreters is limited to CPython, but you can use NumPy, the tips described in this story may help you to improve your code performance.</p><p>This is an open topic, and you have a lot of potential work to do:</p><ul><li>Compare the speed of the implementations yourself and share the results.</li><li>Compare the memory (RAM) consumption of the solutions.</li><li>Write a C++ code dedicated to solving scanline stereo vision efficiently.</li><li>Improve the NumPy code performance.</li><li>Improve the Numba-accelerated code performance.</li><li>Implement the <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e#2c32">time-efficient</a> algorithm effectively in Python.</li><li>Try other Python JIT compilers: <a href="https://jax.readthedocs.io/en/latest/">JAX</a>, <a href="https://pypy.org/">PyPy</a>, etc.</li><li>Is Python slow by design, and what features should be avoided to be able to write its efficient interpreter?</li><li>How do you know whether your Python code is fast enough and whether you can stop optimising it?</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c7dcff677b3c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Scanline Stereo Vision]]></title>
            <link>https://medium.com/@valeriy.krygin/scanline-stereo-vision-85ff252ec521?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/85ff252ec521</guid>
            <category><![CDATA[computer-vision]]></category>
            <category><![CDATA[graph-algorithms]]></category>
            <category><![CDATA[stereo-vision]]></category>
            <category><![CDATA[geometry]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Thu, 01 Aug 2024 08:22:27 GMT</pubDate>
            <atom:updated>2024-08-31T16:36:37.535Z</atom:updated>
            <content:encoded><![CDATA[<h4>Solving Stereo Vision Problems using Dynamic Programming</h4><p>In stories dedicated to <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">dynamic programming</a>, I mentioned the stereo vision problem. The time has come to explain and demonstrate one of its possible variations and its solution. Solving it is an essential step in building 3D models from images.</p><p>Source code: <a href="https://github.com/definability/dynamic_programming_chain_cpp">definability/dynamic_programming_chain_cpp</a>. I license the code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it. However, the code uses the <a href="https://cimg.eu/">CImg Library</a> licensed under the terms of the <a href="http://www.cecill.info/licences/Licence_CeCILL_V2-en.html">CeCILL</a>. When you use any part of its code or any code that uses it (any file in the examples directory), read the license text carefully and follow it strictly.</p><h3>Table of Contents</h3><ul><li><a href="#5145">Introduction</a></li><li><a href="#ded5">Geometry</a><br>- <a href="#00d7">Pinhole Camera</a><br>- <a href="#89f9">Two Cameras</a><br>- <a href="#d191">The Intuition Behind Photogrammetry</a></li><li><a href="#4664">The Optimisation Problem</a><br>- <a href="#a5ff">Data Term</a><br>- <a href="#dd14">Smoothness Term</a><br>- <a href="#9fd3">The Problem</a></li><li><a href="#c13e">Implementation</a></li><li><a href="#f42f">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>Take a look at the demonstration of the final result. I placed an apple on a piece of cloth and took two photos. Between them, I moved my camera in a way described further. The greyscale part of the image displays the disparity map, where brighter colours correspond to the closer objects and darker colours correspond to the farther objects. The transition shows the original image and the disparity map in the same picture for an easier comparison.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*h8yO-jkyu0hIdmTwLIPytA.png" /><figcaption>Visualisation of the stereo vision solver result. Image by the Author.</figcaption></figure><p>The stripes on the disparity map are caused by the flaws of the described algorithm. Depth perception is a complicated problem, and fast algorithms are usually imprecise. However, we must begin with something.</p><p>If you want to learn more about computer vision, I recommend getting your free copy of <a href="https://szeliski.org/Book/">Computer Vision: Algorithms and Applications, 2nd ed.</a> by <a href="https://scholar.google.com/citations?user=3_u1jHQAAAAJ">Richard Szeliski</a>, from the official website. It is nice to know that “<a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/Scharstein-IJCV02.pdf">A taxonomy and evaluation of dense two-frame stereo correspondence algorithms</a>” is the most cited work with his co-authorship by today (August 2024).</p><h3>Geometry</h3><p>First, I should explain the basic geometric reasoning behind the problem. As far as we work with scanline stereo vision, it is enough to consider a 2D world with cameras making 1D images instead of a 3D world with 2D photos.</p><h4>Pinhole Camera</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rlcpaQODCx3cDhpPtenkTg.png" /><figcaption>Pinhole camera model. Drawing by the Author.</figcaption></figure><p>The figure depicts the image formation on the basic camera model called the <a href="https://en.wikipedia.org/wiki/Pinhole_camera_model">pinhole camera</a>. The hatched rectangle is the camera body. Point <em>C</em> is a hole in the camera body (aperture). The camera’s focal length, <em>f</em>, is the distance from the aperture to the opposite side of the box (where the film is located). The dash-dot line coming through the aperture is called the <a href="https://en.wikipedia.org/wiki/Optical_axis">optical axis</a>.</p><p>The camera takes a photo of two points: <em>X</em> and <em>Y</em>. The camera film captures only those light rays reflected from (or emitted by) the points that come through the small aperture. Suppose the aperture is small enough to get a sharp image of the objects but large enough to avoid unwanted quantum effects. Thus, if we draw a straight line from the point through the aperture, the intersection of the line with the film is the image of the point. The drawing shows that the line <em>Y′cX′c</em> is the image of the line <em>YX</em>, and it is flipped around the camera’s optical axis. To achieve a more compact drawing and a more straightforward visual analysis, we can flip the image of the points around the frontal camera side — this gives us the line <em>YcXc</em>.</p><h4>Two Cameras</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9yhwXbb385Dm3XKsA2QL5w.png" /><figcaption>Binocular setup of pinhole cameras. Drawing by the Author.</figcaption></figure><p>Given two pinhole cameras, <em>L</em> and <em>R</em>, with identical directions and focal lengths, <em>f</em>, we place them on the same rack <em>LR</em>. The images simultaneously produced by these cameras are called stereo pairs.</p><p>We throw perpendicular <em>XX′</em> from point <em>X</em> to line <em>LR</em>. The lines <em>XX′</em>, <em>LL′</em>, and <em>RR’</em> are parallel. A cut by transversal <em>XL</em> creates internal equal alternate angles <em>XLL′</em> and <em>LXX′</em>, which I call <em>α</em>. Other internal alternate angles, <em>XRR′</em> and <em>RXX′</em>, are identical, and I called them <em>β</em>.<br>We have similar triangles. Considering <em>LL′ = RR′ = f</em>,</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FrQRsJkKZJAh4n1sEknzfeE&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FrQRsJkKZJAh4n1sEknzfeE&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="552" height="213" frameborder="0" scrolling="no"><a href="https://medium.com/media/4a606200e9f423178a70271f26afb670/href">https://medium.com/media/4a606200e9f423178a70271f26afb670/href</a></iframe><p>If we add the two equations and use <em>LX′ + RX′ = LR</em>, we get</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FeuaTxrepeV4wYGkXfBeeNW&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FeuaTxrepeV4wYGkXfBeeNW&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="610" height="169" frameborder="0" scrolling="no"><a href="https://medium.com/media/5d260ae570b183c6d2053022c8c6adf0/href">https://medium.com/media/5d260ae570b183c6d2053022c8c6adf0/href</a></iframe><p>If we know the distance <em>LR</em> between two cameras with the known focal length <em>f</em>, we can calculate the distance from the rack to point <em>X</em> using the coordinates of its projections (images) on the cameras’ films. Moreover, we did not use the projections’ coordinates — instead, we used their relative position on two cameras — <a href="https://en.wikipedia.org/wiki/Binocular_disparity">disparity</a>. Let me show you another example to clarify the statement:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_UIDRhE6srWZYo5mQq6nRg.png" /><figcaption>Binocular setup of pinhole cameras. Drawing by the Author.</figcaption></figure><p>The main difference between point <em>X</em> from the previous drawing and point Y from this drawing is that <em>X</em> is located between the two cameras while <em>Y</em> stays by the left side of both, and so are its projections. The first chain of the systems of equations is the same:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FjA3CKkipSavLJxhwsSNoPp&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FjA3CKkipSavLJxhwsSNoPp&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="555" height="213" frameborder="0" scrolling="no"><a href="https://medium.com/media/7c692d16585ecc7d0666abf2654616aa/href">https://medium.com/media/7c692d16585ecc7d0666abf2654616aa/href</a></iframe><p>However, now <em>LY′ + RY′</em> is not equal to <em>LR</em>. Instead, it is <em>RY′ - LY′ = LR</em>, implying the need to subtract the first equation from the second one:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FiiyfQYcuYzchEZ2Yyoudp&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FiiyfQYcuYzchEZ2Yyoudp&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="586" height="169" frameborder="0" scrolling="no"><a href="https://medium.com/media/2502ec570f855796846ac32754f415c3/href">https://medium.com/media/2502ec570f855796846ac32754f415c3/href</a></iframe><p>Thus, the distance to point <em>Y</em> depends on the focal length <em>f</em> of the cameras, the distance <em>LR</em> between them, and the disparity of the projections of point <em>Y</em>.</p><p>Please note that the angles <em>α</em> and <em>β</em> will become very close (or equal) when <em>YY′</em> goes to infinity. Moreover, this can happen in practice because the pixels on the images are discrete.</p><h4>The Intuition Behind Photogrammetry</h4><p>Let me explain the idea of how to build a 3D model of something using such a simple input:</p><ol><li>Imagine the cameras to be eyes and the rack to be a skull.</li><li>When two eyes look at the wall or any other far object (the farther — the better), they look almost in the same direction.</li><li>If both eyes are closed, objects closer to them may double. The closer the objects, the stronger the doubling. This effect can also be observed in 3D movies watched without spectacles.</li><li>Closing one eye and moving the head from side to side will create an illusion of the motion of objects closer to the eyes. The same effect can be achieved by alternately closing each eye. The closer the objects, the more severe the motion. For example, a finger near the face moves farther than the display between the finger and the wall. This effect is called <a href="https://en.wikipedia.org/wiki/Parallax">parallax</a>.</li><li>Very distant objects will not move. Consider watching stars from a moving car.</li></ol><p>Please note that this experiment does not provide information about the absolute distance to the objects — it can only help us understand which objects are farther or closer to the eyes. However, photos taken by cameras with known parameters allow us to estimate distances and build 3D models of the objects. A science dedicated to this procedure is <a href="https://en.wikipedia.org/wiki/Photogrammetry">photogrammetry</a>.</p><h3>The Optimisation Problem</h3><p>The problem is easy to solve when we know the projections of the observed points in space. As you may have guessed, finding which pixels of the images correspond to the same points in space is a complicated task.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XsSOToU0cBIDV2r2NXrHnA.png" /><figcaption>Building the correspondence between two scanlines of pixels from different cameras. Picture by the Author.</figcaption></figure><p>The figure shows two scanlines from two images obtained from the two cameras described in the previous section. The top row is from the left camera, and the second is from the right camera. Different patterns correspond to different colours. The task is to find an injective mapping representing the correspondence between the pixels of the two cameras. The mapping is called <em>d</em>, and its value in <em>(y, x)</em> is the displacement between pixel <em>(y, x)</em> on the right image and the corresponding pixel on the left image. The figure shows the following:</p><ul><li>the correspondence may unite pixels from the same column as well as from the different columns;</li><li>the arrows do not go right because when a camera moves right, the projections of still objects move left;</li><li>multiple pixels from the top row may correspond to a single pixel from the second row;</li><li>the second row may contain pixels that do not have twins in the first row.</li></ul><h4>Data Term</h4><p>It looks simple: for each pixel of one image, find the closest pixel of the same colour on another image — and the problem is solved, right? In reality, the colours are distorted, so two pixels from different images having the same colour may not mean they are the projections of the same point in space, and projections of the same point may have different colours. However, in the simplest case, we can say that the colours of the projections of the same point are close. We can express this mathematically.</p><p>Given two images, <em>ℓ</em> and <em>r</em>, with width <em>w</em> and height <em>h</em>, find such disparity map <em>d</em> that the sum of differences of colours of the corresponding pixels is minimal. Additionally, I introduce a set <em>P</em> of pixels and a maximum possible disparity <em>Dmax</em>:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FfxMNDjSjt1Hpw1ihBdMMBT&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FfxMNDjSjt1Hpw1ihBdMMBT&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="365" height="268" frameborder="0" scrolling="no"><a href="https://medium.com/media/59a27f7a778baa39ff5bbc4dab6742e3/href">https://medium.com/media/59a27f7a778baa39ff5bbc4dab6742e3/href</a></iframe><p>This part of the penalty is called the data term.</p><h4>Smoothness Term</h4><p>Formalising assumptions regarding the surface shape we want to reconstruct is essential in creating 3D models from photos. The output can be restricted to <a href="https://flame.is.tue.mpg.de/">human faces</a>, cars, buildings, chairs, etc. In this story, I will stick to a simple and generic approach by saying that the scene may consist of multiple objects (sharp transitions in the disparity map are allowed), but the objects should be smooth (the neighbour elements of the disparity map should be similar). I will use the <a href="https://en.wikipedia.org/wiki/Iverson_bracket">Iverson bracket</a> to describe a function penalising any difference in neighbouring disparities equally:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fat4acmKwsGGRcgbi3MmS4t&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fat4acmKwsGGRcgbi3MmS4t&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="500" height="300" frameborder="0" scrolling="no"><a href="https://medium.com/media/995a88778b5dd85a1cbca5b019367650/href">https://medium.com/media/995a88778b5dd85a1cbca5b019367650/href</a></iframe><p>This part of the penalty is called the smoothness term.</p><h4>The Problem</h4><p>By adding the two terms and multiplying the smoothness term by a constant, we get the optimisation problem:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F5GbEtESHbgUofkEZ6MP6S9&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F5GbEtESHbgUofkEZ6MP6S9&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="438" height="384" frameborder="0" scrolling="no"><a href="https://medium.com/media/dea13a91071da380cdb2f2f273853c1b/href">https://medium.com/media/dea13a91071da380cdb2f2f273853c1b/href</a></iframe><p>A penalty function incorporating a data term and such smoothness term is known as the <a href="https://en.wikipedia.org/wiki/Potts_model#Generalized_Potts_model">Potts model</a>.</p><p>To keep the problem simple, we are going to process scanlines independently. This means that the problem can be split into <em>h</em> separate ones. Each problem can be solved using <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">dynamic programming</a> on min-sum semiring.</p><h3>Implementation</h3><p>I use my <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">C++ implementation</a> of the solver. However, it needed to be modified. Originally, it was designed to solve problems with different smoothness penalties for each edge. We do not need to spend so much RAM for this task and will use a 2D array of penalties instead of 3D. Luckily, I <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-5-testing-38e0aa01f18b">covered the code with tests</a>, and they appeared to be sufficient to ensure the code worked even for such challenging tasks.</p><p>To use the dynamic programming solvers, we need to open the images, build the corresponding chain graphs for each scanline, and write the output to an image. I could leverage <a href="https://opencv.org/">OpenCV</a> installed via <a href="https://ubuntu.com/server/docs/package-management">apt</a>, but it was compiled with the <a href="https://gcc.gnu.org/onlinedocs/libstdc++/">GNU C++ Library</a> (libstdc++), so its ABI is incompatible with <a href="https://libcxx.llvm.org/">libc++</a> from LLVM that we use for this project to benefit from the features of C++23. It is August 2024, and not all <a href="https://en.cppreference.com/w/cpp/compiler_support/23">C++23 features</a> are supported by mainstream compilers and standard libraries. Instead, I decided to use the <a href="https://cimg.eu/">CImg Library</a>. It is a header-only library that can do everything I need. The most complicated thing about it is the licensing. The library uses the <a href="http://www.cecill.info/licences/Licence_CeCILL_V2-en.html">CeCILL</a> license, and you must read its conditions carefully before using it in your projects.</p><p>The implementation has a few peculiarities: it uses <a href="https://en.cppreference.com/w/cpp/language/modules">C++20 modules</a> and the <a href="https://en.cppreference.com/w/cpp/language/member_functions#Explicit_object_member_functions">explicit object member function</a>, also known as <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0847r7.html">deducing this</a>, instead of <a href="https://en.cppreference.com/w/cpp/language/crtp">CRTP</a>. I briefly explained the <a href="https://en.cppreference.com/w/cpp/language/member_functions#Explicit_object_member_functions">explicit object member function</a> in <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">Dynamic Programming on Chain Graphs. Part 4: The Implementation</a>. Also, I needed to <a href="https://en.cppreference.com/w/cpp/language/friend">befriend</a> the base class by the derived classes to expose their <a href="https://en.cppreference.com/w/cpp/language/access#Private_member_access">private</a> member functions to it.</p><p>The example comprises two major parts: <a href="https://github.com/definability/dynamic_programming_chain_cpp/blob/master/examples/scanline_stereo_vision.cpp">UI</a> (command-line user interface) and <a href="https://github.com/definability/dynamic_programming_chain_cpp/blob/master/examples/scanline_stereo_vision_solver.ixx">solvers</a>. The UI part performs the input reading and validation, picks the solver, and provides the parameters. Solvers allocate memory for the graph and call the needed algorithm implementation.</p><p>You can use the <a href="https://vision.middlebury.edu/stereo/data/">Middlebury Stereo Datasets</a> to check how this code works. If you want to use the images and publish them somewhere (on your GitHub, in your blog or elsewhere), find out how to do this right. Currently (August 2024), the website states that those who publish the images or disparity maps are requested to cite the appropriate paper(s).</p><h3>Conclusion and Further Directions</h3><p>This story explains the geometry behind stereo vision and a simple problem formulation that can be solved using a dynamic programming approach on chain graphs on (min, +) semirings; technically, this is a Dijkstra algorithm you may know from Computer Science classes. Thus, this writing connects school geometry, basic algorithms and data structures, and modern programming to solve a problem of machine spatial perception. Sounds exciting, right?</p><p>For those who want to dig deeper:</p><ul><li>Implement the algorithm using another programming language.</li><li>Improve the application performance by manually using <a href="https://en.wikipedia.org/wiki/Single_instruction,_multiple_data">SIMD</a> instructions (<a href="https://www.intel.com/content/www/us/en/support/articles/000005779/processors.html">SSE</a>, <a href="https://en.wikipedia.org/wiki/Advanced_Vector_Extensions">AVX</a>, etc).</li><li>Read more about projective geometry to find out how to work with arbitrarily positioned cameras.</li><li>Learn more algorithms, such as <a href="https://en.wikipedia.org/wiki/Semi-global_matching">Semi-global matching</a> (SGM), <a href="http://usim.org.ua/arch/2023/3/4.pdf">Markov Chain Monte Carlo</a> (MCMC), <a href="https://pub.ista.ac.at/~vnk/papers/TRW-S-PAMI.pdf">Sequential Tree-reweighted Message Passing</a> (TRW-S), <a href="https://discovery.ucl.ac.uk/id/eprint/13383/1/13383.pdf">Boykov-Kolmogorov Max-Flow</a> (BK Max-Flow), or any other.</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=85ff252ec521" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse Engineering a Videogame. Part 2. Modify the Game]]></title>
            <link>https://medium.com/@valeriy.krygin/reverse-engineering-a-videogame-part-2-modify-the-game-db4ee9ed90e3?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/db4ee9ed90e3</guid>
            <category><![CDATA[assembly-language]]></category>
            <category><![CDATA[debugging]]></category>
            <category><![CDATA[hacking]]></category>
            <category><![CDATA[reverse-engineering]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Mon, 01 Jul 2024 10:16:42 GMT</pubDate>
            <atom:updated>2024-07-21T14:29:08.524Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using CheatEngine and Ghidra to modify the game behaviour</h4><h3>Table of Contents</h3><ul><li><a href="#94df">Introduction</a></li><li><a href="#9c15">Create and Debug a Process</a></li><li><a href="#c16a">Should We Go Deeper?</a><br>- <a href="#86df">These Constants Come from Elsewhere</a><br>- <a href="#a959">Looking for the Origins of the Acceleration</a></li><li><a href="#012c">Where is the String?</a></li><li><a href="#89b2">An Alternative Method</a></li><li><a href="#63fc">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>In <a href="https://medium.com/@valeriy.krygin/reverse-engineering-a-videogame-part-1-know-your-tools-7906f9bd0e3e">Part 1</a>, we began reverse engineering an open-source version of <a href="https://storm-devs.github.io/storm-engine/">Storm Engine</a> to change the default time acceleration in <a href="https://github.com/storm-devs/sd-teho-public">Sea Dogs: To Each His Own</a>, shortening the time needed in sea battles to chase enemies (or retreat). The engine’s license is <a href="https://www.gnu.org/licenses/gpl-3.0.en.html">GPLv3</a>, so reversing it must be okay. I chose the <a href="https://github.com/storm-devs/storm-engine/releases/tag/beta4">executable compiled in release mode</a> (without Steam), so the actions must be fun. I bought the <a href="https://store.steampowered.com/news/app/223330">Steam version of the game</a> to use the original assets and not violate the copyrights. For dynamic code analysis, I use <a href="https://www.cheatengine.org/">CheatEngine</a>, and for static code analysis, I use <a href="https://ghidra-sre.org/">Ghidra</a>. Let me begin the new hacking session.</p><h3>Create and Debug a Process</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g0y1ipPpOCaxH4bu9tCYRA.png" /><figcaption>Creating a process. Screenshot by the Author.</figcaption></figure><p>Launch the game with Cheat Engine using File -&gt; Open Process; in the new window, use File -&gt; Create Process. Select the executable engine.exe. The debugger starts the application and pauses immediately. We want to find the constants container creation moment. When nothing is initialised, the engine.exe+1261BF0 contains zero. Go to the Memory Viewer’s bottom tab (the one with memory, not with instructions), and Go To (Ctrl+G) that memory chunk.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*2eqosvVrmYaaTONo20xXjw.png" /><figcaption>Go to a memory address. Screenshot by the Author.</figcaption></figure><p>The byte with this address will appear on the top-left cell of the memory view. Use the right mouse button, click on it, and select Data Breakpoint -&gt; Break on Write.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*J8q5QJhh-LmE6ObNYYAw5w.png" /><figcaption>Create a breakpoint on writing to the memory. Screenshot by the Author.</figcaption></figure><p>Run (F9) and wait for the debugger to stop the application. Success:</p><pre>engine.exe+257786: 48 89 7B 40 - mov [rbx+40],rdi<br>engine.exe+25778A: 41 B0 01    - mov r8b,01 ;; &lt;- here</pre><p>Remove the current breakpoint, Go To (Ctrl+G) the container address with 0x18 offset (engine.exe+1261BF0+0x18 in the memory view) and set a breakpoint on write. Run (F9) the game again. Execution stopped right after the instruction we already know:</p><pre>engine.exe+268677: 4C 89 6E 18          - mov [rsi+18],r13<br>engine.exe+26867B: C7 44 24 30 FFFFFFFF - mov [rsp+30],FFFFFFFF ;; &lt;- here</pre><p>All the constants are already in place, which means that R13 contains a pointer to the container allocated elsewhere. To discover this further, relaunch the game, set a breakpoint on write for engine.exe+1261BF0, and Run (F9). Yes, we are on the right path.</p><pre>engine.exe+268645 - 48 8B 86 60110000     - mov rax,[rsi+00001160]<br>engine.exe+26864C - 4D 8B 6C 04 40        - mov r13,[r12+rax+40]<br>engine.exe+268651 - 45 32 D2              - xor r10b,r10b<br>engine.exe+268654 - EB 21                 - jmp engine.exe+268677<br>;; commands we jump over<br>engine.exe+268677 - 4C 89 6E 18           - mov [rsi+18],r13</pre><p>The following expression gives the pointer to the container:</p><pre>readQword(R12 + readQword(RSI + 0x1160) + 0x40)</pre><p>Look at this code in Ghidra (press G and enter 0x140268677). It says that this is a part of a function beginning at 0x1402682F0. Return to Cheat Engine, quit the game, and start over with the breakpoint at the engine.exe+0x268677. Use Ctrl+G to find the address fast. After reaching the function beginning, use F8 and watch the address</p><pre>readQword(R12 + readQword(RSI + 0x1160) + 0x40)</pre><p>You can use Lua in “Add Address Manually”, which is handy in our case.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/264/1*H24Bs4VHku6HAolzlBtvoA.png" /><figcaption>Using Lua in “Add address”. Screenshot by the Author.</figcaption></figure><p>The needed values appear in the container once we reach</p><pre>engine.exe+26832E: 48 8B F1 - mov rsi,rcx</pre><p>Almost the very beginning. Look at the Return Address stack (the bottom right panel of Memory View).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/829/1*qD5z8_9dg0K_1GEBlcu_BQ.png" /><figcaption>The call stack (right bottom) and the information about the needed address. Screenshot by the Author.</figcaption></figure><p>The function caller is</p><pre>engine.exe+258865: 49 8B CE          - mov rcx,r14<br>engine.exe+258868: E8 83FA0000       - call engine.exe+2682F0 ;; &lt;- here<br>engine.exe+25886D: 4D 89 A6 B8110000 - mov [r14+000011B8],r12</pre><p>Quit the game, start it with the debugger again and place a breakpoint at engine.exe+258865. Once we reach it, the container pointer is stored at</p><pre>readQword(R12 + readQword(R14 + 0x1160) + 0x40)</pre><p>Return to Ghidra. It gave the name lVar1 to the R14. The assignment of this variable happens at</p><pre>lVar1 = *(longlong *)(param_1 + 0x40);</pre><p>which corresponds to</p><pre>engine.exe+258737: 4C 8B 76 40 - mov r14,[rsi+40]</pre><p>Scan memory to find what holds the same value as RSI. Many references emerge, but we are interested in one with a persistent address. The only likely candidate is the engine.exe+114B558.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*6P6AsYhqoI8UdsalsB4_BQ.png" /><figcaption>Scanning for the contents of RSI. Screenshot by the Author.</figcaption></figure><p>Let us create a new entry in the address list: a pointer engine.exe+114B558 with offsets 0x40, 0x1160, 0x40 (R12 is zero, so let us suppose that only 0x40 affects the offset on this level), and 0. We have an address of a container from which the constants are copied.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*_HF4DfYuMt5dwH-fsnndyg.png" /><figcaption>Creating a chain of pointers in Cheat Engine. Screenshot by the Author.</figcaption></figure><h3>Should We Go Deeper?</h3><p>Remove all breakpoints and restart the game in debug mode again. Break on Write to engine.exe+114B558. Run (F9) until the debugger stops. It stopped here:</p><pre>engine.exe+2BE6B: 48 89 0D E6F61101 - mov [engine.exe+114B558],rcx<br>engine.exe+2BE72: 48 8B 05 375D2301 - mov rax,[engine.exe+1261BB0] ;; &lt;- here</pre><p>Now, the pointer engine.exe+114B558 contains a value. Let us break on writing to this value (you can copy it from RCX) with a 0x40 offset and Run (F9). Debugger stops at</p><pre>engine.exe+257786: 48 89 7B 40 - mov [rbx+40],rdi<br>engine.exe+25778A: 41 B0 01    - mov r8b,01 ;; &lt;- here</pre><p>Take the new value (you can copy it from RDI) with 0x1160 offset and break on writing to it. Run (F9) and see that we are coming closer to our current aim:</p><pre>engine.exe+277C56: E8 25F7F7FF - call engine.exe+1F7380<br>engine.exe+277C5B: 4C 89 37    - mov [rdi],r14<br>engine.exe+277C5E: 48 6B C5 58 - imul rax,rbp,58 ;; &lt;- here</pre><p>Break on write to the new value (you can copy it from R14) + 0x40. After Run (F9), we are in</p><pre>engine.exe+262EA4: E8 43421700    - call engine.exe+3D70EC<br>engine.exe+262EA9: 48 8B 4F 40    - mov rcx,[rdi+40]<br>engine.exe+262EAD: FF 15 7D271800 - call qword ptr [engine.exe+3E5630]<br>engine.exe+262EB3: 48 89 5F 40    - mov [rdi+40],rbx<br>engine.exe+262EB7: 48 8B 5C 24 30 - mov rbx,[rsp+30] ;; &lt;- here<br>engine.exe+262EBC: 48 83 C4 20    - add rsp,20<br>engine.exe+262EC0: 5F             - pop rdi<br>engine.exe+262EC1: C3             - ret</pre><p>Now, the pointer points to a chunk of memory with values. The offset 0x65C0 and 0x7F3BC hold values 0.0F. After two more F9, the value is changed to 1.0F, but the address changes every time. For this code segment, Ghidra shows</p><pre>_Dst = (void *)mi_new(iVar1);<br>memcpy(_Dst,*(void **)(param_2 + 0x40),(ulonglong)*(uint *)(param_2 + 0x48));<br>mi_free(*(undefined8 *)(param_2 + 0x40));<br>*(void **)(param_2 + 0x40) = _Dst;</pre><p>A memory is allocated for _Dst, then a memory chunk pointed by param_2 + 0x40 (RDI + 0x40) is copied to _Dst, and param_2 + 0x40 is replaced by the _Dst. The procedure looks like <a href="https://en.cppreference.com/w/c/memory/realloc">realloc</a> or even <a href="https://en.cppreference.com/w/cpp/container/vector/push_back">push_back</a>.</p><p>Another change in this pointer happens before</p><pre>engine.exe+263057: FF 15 D3251800 - call qword ptr [engine.exe+3E5630]<br>engine.exe+26305D: 48 89 7B 40    - mov [rbx+40],rdi<br>engine.exe+263061: 39 74 24 68    - cmp [rsp+68],esi ;; &lt;- here</pre><p>The normal speed constant appears in the container after five reaches of this instruction and before the third call of engine.exe+262EB7.</p><h4>These Constants Come from Elsewhere</h4><p>Restart the game and place a breakpoint at engine.exe+26305D. Run (F9) five times, and then make a Step Over (F8). Now, we have a pointer to the container that will hold the normal speed constant. Place a breakpoint on write to the location for the normal speed (offset 0x65C0). Debugger stops at</p><pre>VCRUNTIME140.memcpy+11E: C3 - ret</pre><p>It is a standard <a href="https://en.cppreference.com/w/cpp/string/byte/memcpy">memcpy</a>. Make a Step Over (F8) to know where it was called from. It moves us to</p><pre>engine.exe+263090: E8 57401700 - call engine.exe+3D70EC<br>engine.exe+263095: 01 7B 48    - add [rbx+48],edi ;; &lt;- here</pre><p>Open Ghidra. The corresponding code segment looks interesting:</p><pre>do {<br>  uVar5 = *(uint *)(*(longlong *)(param_1 + 0x5d50) + 8 + uVar4 * 0xc);<br>  memcpy((void *)((ulonglong)*(uint *)(param_2 + 0x48) + *(longlong *)(param_2 + 0x40)),<br>         *(void **)(*(longlong *)(param_1 + 0x5d50) + uVar4 * 0xc),(ulonglong)uVar5);<br>  *(int *)(param_2 + 0x48) = *(int *)(param_2 + 0x48) + uVar5;<br>  uVar5 = (int)uVar4 + 1;<br>  uVar4 = (ulonglong)uVar5;<br>} while (uVar5 &lt; param_4);</pre><p>Restart the game and place a breakpoint at engine.exe+26305D. Reach it five times with Run (F9). Then, make Step Over (F8). Get the address of the normal speed constant. Subtract 8. Place a breakpoint at engine.exe+263095 with condition</p><pre>RBP == readQword(readQword(getAddress&#39;engine.exe&#39; + 0x114B558) + 0x40) and RAX == address - 8</pre><p>Yes, you can use engine.exe address with <a href="https://wiki.cheatengine.org/index.php?title=Lua:getAddress">getAddress</a>. It is not part of standard Lua but of the Cheat Engine Lua API.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*Dlu5OqCm5nAFN_MreNM0nQ.png" /><figcaption>Designing another chain of pointers in Cheat Engine. Screenshot by the Author.</figcaption></figure><p>Add a pointer engine.exe+114B558 with offsets 0x40, 0x5D50, 0, and 0. Stop on write in the value corresponding to the offset 0x5D50. We stopped at</p><pre>engine.exe+262F52: 48 89 BD 505D0000 - mov [rbp+00005D50],rdi<br>engine.exe+262F59: 4C 8D 5C 24 70    - lea r11,[rsp+70] ;; &lt;- here</pre><p>Watch the value corresponding to the third offset (the first zero). The constant is prepared, and we are at</p><pre>engine.exe+262F94: 48 8B 8D 505D0000 - mov rcx,[rbp+00005D50]<br>engine.exe+262F9B: 48 89 04 0A       - mov [rdx+rcx],rax<br>engine.exe+262F9F: 48 8B 85 505D0000 - mov rax,[rbp+00005D50] ;; &lt;- here</pre><p>From the code, we can see that RAX holds the value pointed by RDX + RCX, and RAX contains the same value as pointed by RSP + 0x70. They both point to a float of 1.0f. You can use the following Lua code to check this:</p><pre>print(string.format(&quot;0x%X =&gt; 0x%X, 0x%X&quot;, RDX + RCX, readQword(RDX + RCX), RAX))<br>print(string.format(&quot;0x%X, 0x%X =&gt; %f&quot;, RAX, readQword(RSP+0x70), readFloat(RAX)))</pre><p>Let us return to</p><pre>engine.exe+263095: 01 7B 48 - add [rbx+48],edi</pre><p>Restart the game and put a conditional breakpoint here. The condition is complex. We want to catch the moment when the engine adds the normal speed constant. Thus, we want to stop when RAX contains the address of the constant (remember, it has 0x65C0 offset):</p><pre>root = getAddress&#39;engine.exe&#39; + 0x114B558<br><br>levelFirst = readQword(readQword(root) + 0x40)<br>levelSecond = readQword(levelFirst + 0x1160)<br>container = readQword(levelSecond + 0x40)<br>normalSpeedPointer = container + 0x65C0<br><br>return RBP == levelFirst and RAX == normalSpeedPointer</pre><p>It works. Checking the same for deceleration (0x7F3BC offset) ensures we are on the right path.</p><h4>Looking for the Origins of the Acceleration</h4><p>We want to know what triggers the acceleration change (0x81B1F offset). The container is populated sequentially. Moreover, it seems filled with relatively small values (1–8 bytes). Let us stop when RAX points somewhere near before the acceleration constant pointer:</p><pre>root = getAddress&#39;engine.exe&#39; + 0x114B558<br><br>levelFirst = readQword(readQword(root) + 0x40)<br>levelSecond = readQword(levelFirst + 0x1160)<br>container = readQword(levelSecond + 0x40)<br>doubleSpeedPointer = container + 0x81B1F<br><br>return RBP == levelFirst and RAX &gt;= doubleSpeedPointer - 8</pre><p>After numerous steps out (Shift+F8), steps into (F7), steps over (F8), and multiple game relaunches to investigate the origins of the 2.0 value, I finally reached this interesting instruction:</p><pre>engine.exe+26AC30: 48 8B 89 B0100000 - mov rcx,[rcx+000010B0]<br>engine.exe+26AC37: FF 15 03A41700    - call qword ptr [engine.exe+3E5040] ;; &lt;- here</pre><p>Ghidra says this is <a href="https://en.cppreference.com/w/cpp/string/byte/atof">atof</a>, which is promising because we need a floating point value, which is parsed from a string:</p><pre>dVar1 = atof(*(char **)(param_1 + 0x10b0));</pre><p>Moreover, RCX points to a string “2.0”. So, the acceleration factor constant is stored in a string parsed here. Where does the engine get this string? Let us restart the game and set a breakpoint at engine.exe+263095 with the same complex condition</p><pre>root = getAddress&#39;engine.exe&#39; + 0x114B558<br><br>levelFirst = readQword(readQword(root) + 0x40)<br>levelSecond = readQword(levelFirst + 0x1160)<br>container = readQword(levelSecond + 0x40)<br>doubleSpeedPointer = container + 0x81B1F<br><br>return RBP == levelFirst and RAX &gt;= doubleSpeedPointer - 8</pre><h3>Where is the String?</h3><p>Add a string pointed by RCX+0x000010B0 to the address list and watch how it changes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*AZ_wqgXuTvuWklJnhzZ5nQ.png" /><figcaption>Watching the contents of a string. Screenshot by the Author</figcaption></figure><p>After</p><pre>engine.exe+2656C0: 48 8D 8B 98000000 - lea rcx,[rbx+00000098]</pre><p>string in RCX+0x10B0 became</p><pre>// BOAL 07.09.03  Mods on_off mode --&gt;<br>#include &quot;</pre><p>After</p><pre>engine.exe+266D7A: 48 8B CB - mov rcx,rbx</pre><p>string in RCX+0x10B0 became “2.0”. This change means that the value was written to RBX somewhere before. Let us relaunch the game, set a breakpoint at engine.exe+263095 with the same complex condition, then run to engine.exe+2656C0, and now inspect the string pointed by RBX+0x10B0 (not only RCX+0x10B0). Its value becomes “2.0” after</p><pre>engine.exe+266D58: E8 D3450100 - call engine.exe+27B330</pre><p>One more time. Launch the game, stop at engine.exe+263095 with the same complex condition, then stop at engine.exe+266D58. Now, RCX+0x10B0 contains</p><pre>// BOAL 07.09.03  Mods on_off mode --&gt;<br>#include &quot;</pre><p>and RBX+0x10B0 contains “return”. Step Into (F7) and Step Over (F8) until something changes in RCX+0x10B0 or RBX+0x10B0. Interestingly, RBX+0x10B0 becomes a null pointer after</p><pre>engine.exe+27B344: 48 8D 99 A8100000 - lea rbx,[rcx+000010A8]</pre><p>However, the next command is</p><pre>engine.exe+27B34B: 48 8B 13 - mov rdx,[rbx]</pre><p>The use of [RBX] means that RBX points to something meaningful. Use print(readString(readQword(RBX))) to fetch its contents, which is</p><pre> 2.0;<br>}<br><br>void SetShowWindowParameters(bool TVus </pre><p>There are many .c and .h files in the game folder. Let us use grep to find these lines:</p><pre>find . -name &quot;*.[ch]&quot; -type f -exec fgrep -H -B 5 &quot;void SetShowWindowParameters&quot; {} \;</pre><p>The result is</p><pre>./PROGRAM/interface/interface.c-float GetSeaTimeScale()<br>./PROGRAM/interface/interface.c-{<br>./PROGRAM/interface/interface.c-        return 2.0;<br>./PROGRAM/interface/interface.c-}<br>./PROGRAM/interface/interface.c-<br>./PROGRAM/interface/interface.c:void SetShowWindowParameters(bool TVused, int w,int h, int l,int t,int r,int b)</pre><p>This is a function from <a href="https://github.com/storm-devs/sd-teho-public/blob/d897194748fb134b855fb5f85bd3b7333cf00e69/program/interface/interface.c#L1856-L1859">program/interface/interface.c</a>, which we can easily modify. These *.c and *.h files are shipped with the game and are used as configuration files. Storm Engine has its <a href="https://github.com/storm-devs/storm-engine/blob/a68f43df197a50c5177f40209abc109f01f4b114/src/libs/core/src/compiler.h#L93">compiler</a> to parse these configuration files.</p><h3>An Alternative Method</h3><p>Yes, we could find this position in the configuration file quicker. For example, we could look for the “ESCAPE” key in files. The file <a href="https://github.com/storm-devs/sd-teho-public/blob/d897194748fb134b855fb5f85bd3b7333cf00e69/program/controls/init_pc.c#L62">program/controls/init_pc.c</a> contains several mentions of VK_ESCAPE. Ordinary ASCII keys have the prefix “KEY_” there, and you can use “R” in the game to trigger the time acceleration. Here it is:</p><pre>CI_CreateAndSetControls( &quot;&quot;, &quot;TimeScale&quot;, CI_GetKeyCode(&quot;KEY_R&quot;), 0, false );</pre><p>File <a href="https://github.com/storm-devs/sd-teho-public/blob/d897194748fb134b855fb5f85bd3b7333cf00e69/program/seadogs.c#L1167-L1185">program/seadogs.c</a> contains</p><pre>case &quot;TimeScale&quot;:<br>    // ...<br>        else<br>        {<br>                SetTimeScale(GetSeaTimeScale());<br>                TimeScaleCounter = 4;<br>Log_SetStringToLog(XI_ConvertString(&quot;Time x2&quot;));<br>                AddPerkToActiveList(&quot;TimeSpeed&quot;);<br>        }<br>break;</pre><p>Here, we can modify the string shown when we accelerate the time.</p><h3>Conclusion and Further Directions</h3><p>We have built a foundation for further exploration of the game. It is nice that players can use those *.c and *.h files to modify the game’s behaviour because it is much easier than patching binaries. However, some things cannot be changed through the configuration files — for example, <a href="https://github.com/storm-devs/storm-engine/blob/a68f43df197a50c5177f40209abc109f01f4b114/src/libs/sea_ai/src/ai_ship.cpp">ship AI</a> and <a href="https://github.com/storm-devs/storm-engine/blob/a68f43df197a50c5177f40209abc109f01f4b114/src/libs/location/src/np_character.cpp">NPC behaviour</a>. The configuration files and constants container we found could be good clues to modifying the AI.</p><p>Hopefully, once upon a time, I will cover amazing techniques like <a href="https://en.wikipedia.org/wiki/DLL_injection">DLL injection</a> and <a href="https://en.wikipedia.org/wiki/Code_cave">code cave</a> use. In the meantime, you can learn and try them yourself.</p><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=db4ee9ed90e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse Engineering a Videogame. Part 1. Know Your Tools]]></title>
            <link>https://medium.com/@valeriy.krygin/reverse-engineering-a-videogame-part-1-know-your-tools-7906f9bd0e3e?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/7906f9bd0e3e</guid>
            <category><![CDATA[reverse-engineering]]></category>
            <category><![CDATA[assembly-language]]></category>
            <category><![CDATA[debugging]]></category>
            <category><![CDATA[hacking]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Sat, 01 Jun 2024 13:32:22 GMT</pubDate>
            <atom:updated>2024-07-01T10:19:23.862Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using CheatEngine and Ghidra to turn a game you like into one you love</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RDV58iYwcAjWsp2dBpjsMw.png" /><figcaption>Know Your Tools. Screenshot by the Author.</figcaption></figure><h3>Table of Contents</h3><ul><li><a href="#a12f">Introduction</a></li><li><a href="#2a3e">Legal Questions</a></li><li><a href="#3cb9">Let the Hacking Begin</a></li><li><a href="#698d">What Changes the Global Game Speed</a><br>- <a href="#c905">The Setter</a><br>- <a href="#dada">Where Does the Setter Caller Get the Value?</a><br> — <a href="#4cf0">Let Us Have a Rest</a><br> — <a href="#8ecf">Back to Work</a></li><li><a href="#09f2">What Changes the Temporary “Constants”?</a></li><li><a href="#2ac7">Are these “Constants” Constant?</a><br>- <a href="#7d9b">Game Acceleration State</a><br>- <a href="#512d">Inspecting Constants Container</a></li><li><a href="#2c30">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>This story is my log of reverse engineering <a href="https://github.com/storm-devs/sd-teho-public">Sea Dogs: To Each His Own</a> to increase the default game speed acceleration because 2x does not look fast enough during heavy sea battles. However, instead of writing a simple trainer, I want to make something more universal and persistent: write a patch for the game binary or find a value in the configuration file if this suffices.</p><p>Reading this page requires familiarity with <a href="https://www.cheatengine.org/">CheatEngine</a> for dynamic code analysis, <a href="https://ghidra-sre.org/">Ghidra</a> for static code analysis (disassembly + decompiler <a href="https://www.nsa.gov/Press-Room/Press-Releases-Statements/Press-Release-View/Article/1805182/attention-ghidra-users-full-source-code-released/">developed by the NSA</a>), and the <a href="https://en.wikipedia.org/wiki/X86_assembly_language#Syntax">Intel syntax</a> of <a href="https://en.wikipedia.org/wiki/X86_assembly_language">x86 Assembly</a>.</p><h3>Legal Questions</h3><p>I chose an open-source version of <a href="https://storm-devs.github.io/storm-engine/">Storm Engine</a> to keep this reverse engineering session legal. This story is dedicated to <a href="https://github.com/storm-devs/sd-teho-public">Sea Dogs: To Each His Own</a> because it is currently the only game supported by the open-source version of the engine. Textures, sounds, and models are not stored on GitHub, so I had to buy the <a href="https://store.steampowered.com/news/app/223330">Steam version of the game</a>. You must not reverse engineer the Steam version of the game until you have qualified legal advice because the <a href="https://store.steampowered.com/subscriber_agreement">Steam Subscriber Agreement</a> forbids reverse engineering. The binaries of Storm Engine residing on GitHub do not have such a limitation as GPL v3.0 does not seem to impose it.</p><p>Is it still fun? Of course. I <a href="https://github.com/storm-devs/storm-engine/releases/tag/beta4">downloaded</a> the release version of the executable of the open-source version of Storm Engine and removed PDB files to pretend to be working with a production executable.</p><h3>Let the Hacking Begin</h3><p>For convenience, modify the engine.ini file after replacing the game binaries with open-source ones: make full_screen = 0 to have a windowed mode to switch between the game and <a href="https://www.cheatengine.org/">CheatEngine</a> without issues. You can also modify the screen_x and screen_y.</p><p>Use a scan to find a memory segment corresponding to the game speed. If we do not know whether it is a floating-point number, a boolean value, or anything else, we can use an “Unknown initial value” scan for 4-byte or 8-byte values. Then, change the speed using the “R” button and do the next search with either “Changed value” or “Unchanged value”, depending on whether you changed the speed or not. You may need to change location, city, or other things to filter out more variables. Keep track of your actions to avoid forgetting whether you changed the speed.</p><p>The value we are looking for has a constant address relative to the program memory beginning: engine.exe+1262528, meaning 0x1262528 (19,277,096) bytes offset. I will call it the global game speed. It is 0x40000000 when the game speed is accelerated, 0x00000000 in the main menu (paused), and 0x3F800000 when the speed is normal. These values match <a href="https://en.wikipedia.org/wiki/Single-precision_floating-point_format">single-precision floating-point</a> numbers 2.0, 0.0, and 1.0 correspondingly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/831/1*Q4jeV7W7wsSFyN3spasMMg.png" /><figcaption>The process of memory scan in CheatEngine. Screenshot by the Author.</figcaption></figure><h3>What Changes the Global Game Speed?</h3><h4>The Setter</h4><p>Find out what changes the global game speed. Use the “Find out what writes to this address” (F6) tool. It shows valuable information and lets you see the command&#39;s disassembler that triggered the change.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xaa15k0kS6J9IHQzik4P7A.png" /><figcaption>Find out what changes the global game speed. Screenshot by the Author.</figcaption></figure><p>The only place where the global game speed is modified is</p><pre>engine.exe+27C7A9: FF 90 C0000000      - call qword ptr [rax+000000C0]<br>engine.exe+27C7AF: F3 0F10 44 24 34    - movss xmm0,[rsp+34]<br>engine.exe+27C7B5: F3 0F11 05 6B5DFE00 - movss [engine.exe+1262528],xmm0 ;; &lt;- here</pre><p>Stop the watch (click the “Stop” button). Go to Ghidra and use “g” to reach the address 0x14027C7B5 because the engine.exe begins at 0x140000000. The decompiled code shows an assignment here:</p><pre>if (*(int *)(plVar14 + 2) == 7) {<br>  (**(code **)(*plVar14 + 0xc0))(plVar14,&amp;local_284);<br>  _DAT_141262528 = local_284; // &lt;- we are here<br>}</pre><p>Before the assignment, the variable local_284 could be modified because its address is passed to a function. The function’s address seems defined in runtime, so we must return to the debugger (we can use the one integrated into CheatEngine) to find the function. Place a breakpoint at engine.exe+27C7A9, where this mysterious function is called, and change the game speed by pressing the “R” button in the game. Step into (F7) the function. We can see the address of its beginning:</p><pre>engine.exe+282F80: 48 83 EC 28 - sub rsp,28</pre><p>In Ghidra, open the address 0x140282F80 (0x140000000 + 0x282F80). The function takes two arguments, the second of which is a pointer. There is only one place where this pointer is used:</p><pre>if (uVar1 == 7) {<br>  uVar2 = *(undefined4 *)(param_1 + 0x28);<br>  *param_2 = uVar2;<br>  return CONCAT71((uint7)(uint3)((uint)uVar2 &gt;&gt; 8),1);<br>}</pre><p>The assignment happens in</p><pre>engine.exe+282FDF: 8B 41 28 - mov eax,[rcx+28]<br>engine.exe+282FE2: 89 02    - mov [rdx],eax ;; &lt;- here</pre><p>Remove the last breakpoint and set a new one at the engine.exe+282FE2. Use Ctrl+G for faster navigation. You can use Lua scripting and “engine.exe” there.</p><p>A value from a memory segment pointed by RCX + 0x28 (param_1 + 0x28) is copied to EAX (uVar2) and then to a memory segment pointed by RDX (param_2). I think param_1 is a pointer to the beginning of an array or a structure. Let us investigate this.</p><p>I use the Add Address Manually button to see what the address RCX + 0x28 points to, specifying a 4-byte float type. It shows the game speed we want to set (1 or 2), which is excellent. During this run, the value of RCX is 0x4F528AF9180. Let us look at the 8-byte HEX value it points to. The result is 0x00007FF7DB037BB8, which is a pointer, as expected. It points to 0x00007FF7DAE124E0, which again looks like a pointer. It points to 0x83485708245C8948, the meaning of which is unclear to me, so let us stop our investigation of this memory chunk for now.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/185/1*wsNLbEbhnUMjxVET3vZOuQ.png" /><figcaption>Add address manually. Screenshot by the Author.</figcaption></figure><p>When I press Run (F9), the debugger stops at the breakpoint on engine.exe+282FE2. This function is called several times more. Once I focus on the game window, the debugger stops at this breakpoint again. This code fragment looks like a setter for different properties. The function receives only two parameters: where to find the property and what value to assign. The decision for where to get the value to assign and the creation of the value itself is made elsewhere.</p><h4>Where Does the Setter Caller Get the Value?</h4><p>Let us find what modifies the property from which the speed is obtained. Using “Find out what writes to this address” (F6) for 0x4F528AF9180+0x28 (remember, 0x4F528AF9180 is the value fetched from RCX from my current debugging session and may be different for you) shows many changes even when I do not change the game speed. This behaviour may mean that this property is an intermediate local variable.</p><p>However, I discovered a clue. I set a breakpoint where the setter is called:</p><pre>engine.exe+27C7A9: FF 90 C0000000 - call qword ptr [rax+000000C0]</pre><p>When I change game speed, I look at the value of RCX. It is different for different game speeds. For double speed, it is 0x4F528AF9180; for normal speed, it is 0x4F528AF9220. The last three hexadecimal digits are changed; the difference is 0xA0 (160 bytes). When I pause the game, the game speed becomes zero, and the value of RCX is 0x4F528AF9180, which is 0x280 (640 bytes, which is four times 160 bytes) behind 0x4F528AF9220. It looks like there is an array of properties with temporary values within. Even though each property serves different purposes, each game speed uses its property, meaning a many-to-one relation between semantics and memory cells. Yet another thing to notice: in all three cases, RCX points to 0x00007FF7DB037BB8.</p><p><strong>Let Us Have a Rest</strong></p><p>We can estimate a property&#39;s size. The distance between the two properties we know is divisible by 160. A property contains a floating-point value starting at 0x28 (40 bytes). The value consumes 4 bytes, meaning each property must occupy at least 44 if the properties are the same size. So, the property size is either 80 or 160 bytes because these are the only numbers not smaller than 44 by which the 160 is divisible.</p><p>Let us write a Lua script to examine the memory chunks nearby using Tools -&gt; Lua Engine (Ctrl+L):</p><pre>temporary_time_pause= 0x4F528AF8F28 -- The value from RCX<br>for i = 0, 8 do<br>  offset = 80 * i<br>  value = readQword(temporary_time_pause + offset)<br>  print(string.format(&quot;%d: Offset 0x%04X: 0x%08X&quot;, i, offset, value))<br>end</pre><p>I get the following output:</p><pre>0: Offset 0x0000: 0x7FF7DB037BB8 <br>1: Offset 0x0050: 0x43E004700430000 <br>2: Offset 0x00A0: 0x7FF7DB037BB8 <br>3: Offset 0x00F0: 0x104760001 <br>4: Offset 0x0140: 0x7FF7DB037BB8 <br>5: Offset 0x0190: 0x31A2043C0001 <br>6: Offset 0x01E0: 0x7FF7DB037BB8 <br>7: Offset 0x0230: 0x5F70696853736E01 <br>8: Offset 0x0280: 0x7FF7DB037BB8</pre><p>We discovered properties we did not know about. I located more than a hundred such values by expanding the loop ranges. The property size is 80 bytes, and many are arranged as a sequence in memory. I do not know how to use this information, but this discovery is pleasant.</p><p><strong>Back to Work</strong></p><p>Leave the breakpoint at</p><pre>engine.exe+27C7A9: FF 90 C0000000 - call qword ptr [rax+000000C0]</pre><p>Another interesting thing happens. When I unpause the game and the debugger stops at the breakpoint, the value of RCX is not the same as it was for the normal game speed, meaning that a separate property is used to unpause the game. The value is 0x4F528AF8DC0, 0x140 (320 bytes) behind the property corresponding to the game pause.</p><p>Let us check whether anything interesting happens if we pause the accelerated game. I have a new value in RCX: 0x51C07698E60, which is 0xA0 ahead of the unpause property. RCX+0x28 points to 1.0F, which is strange. Let us press Run (F9) again. The game speed changed to 1.0F, and the debugger stopped at the breakpoint again. RCX points to the pausing property we discovered before, which holds 0.0F. If the game is accelerated and we press Esc to pause, the game speed resets to normal first, and only then it pauses.</p><p>Let us summarise the properties we discovered:</p><pre>float* unpause = RCX; // 0x4F528AF8DC0 in my case<br>float* decelerate = unpause + 0xA0;<br>float* pause = decelerate + 0xA0;<br>float* accelerated = pause + 0x280;<br>float* normal = accelerated + 0xA0;</pre><p>You can use “Create Header” to create a group of relative addresses. Remember to specify the value contained in RCX instead of just writing RCX as the group address. During this run, it was 0x4F528AF8DC0. Then, you can use “Add Address Manually” with a relative address using +0x0 as the address. Move the new value to the group. Next, you can create a value with the address +0x28 and move it under the newly created property pointer, and you will see a floating point value. Add other properties and check whether they point to the floating point numbers corresponding to the game speed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*-DE95l8C3QjONazlxzxbJQ.png" /><figcaption>Using headers and relative addresses. Screenshot by the Author.</figcaption></figure><p>If we use “Find out what writes to this address” (F6) for the floating-point values we are interested in, we can see many changes during the game&#39;s run. Let us use the fact that the game speed is changed twice when pausing the accelerated game.</p><h3>What Changes the Temporary “Constants”?</h3><p>Return to the game and accelerate it (press R). Leave the breakpoint at</p><pre>engine.exe+27C7A9: FF 90 C0000000 - call qword ptr [rax+000000C0]</pre><p>Press Esc to start pausing the game. The debugger must stop at the breakpoint. Now, use “Find out what writes to this address” (F6) to see what writes to the address corresponding to the pause: pause + 0x28. Press Run (F9). The debugger must stop again at the same breakpoint, and we can see what modifies the floating point number we are interested in. It is</p><pre>engine.exe+282ACB: F3 0F11 49 28 - movss [rcx+28],xmm1</pre><p>Return to Ghidra and go to (G) address 0x140282ACB. It looks like another setter:</p><pre>void FUN_140282a80(longlong param_1,float param_2)<br>{<br>  // ...<br>  *(undefined4 *)(param_1 + 0x10) = 7;<br>  *(float *)(param_1 + 0x28) = param_2; // &lt;- we are here<br>  // ...<br>}</pre><p>Step Out (Shift+F8) jumps to the following place:</p><pre>engine.exe+269C3D: 8B 4E 10          - mov ecx,[rsi+10]<br>engine.exe+269C40: 48 8B 46 18       - mov rax,[rsi+18]<br>engine.exe+269C44: F3 0F10 0C 01     - movss xmm1,[rcx+rax]<br>engine.exe+269C49: 48 8B CF          - mov rcx,rdi<br>engine.exe+269C4C: FF D2             - call rdx<br>engine.exe+269C4E: 4C 8D B6 80110000 - lea r14,[rsi+00001180] ;; &lt;- here</pre><p>This looks promising: the value we find in XMM1 is passed from a pointer, a sum of values in RCX and RAX. I suspect that RAX contains a pointer while RCX contains an offset because only its little part ECX is filled.</p><p>Let us remove the breakpoints, resume the game and accelerate it again. Again, place a breakpoint at</p><pre>engine.exe+27C7A9: FF 90 C0000000 - call qword ptr [rax+000000C0]</pre><p>Pause the game (Esc). When the debugger pauses the application, add a breakpoint at</p><pre>engine.exe+269C44: F3 0F10 0C 01 - movss xmm1,[rcx+rax]</pre><p>Run (F9) the game again. In this run, RAX is 0x4F52BA79000, and RCX is 0x91. Their sum (0x4F52BA79091) points to 0.0f, which means pause. Let us see where the address for the pause property (0x4F528AF8F28) is stored. It is in RDI. Let us turn this breakpoint into a conditional breakpoint. We want to know where the game fetches the acceleration speed. If the address of the property for unpausing is 0x4F528AF8DC0, the condition is</p><pre>RDI == 0x4F528AF8DC0 + 0x140 + 0x280 and readFloat(RCX + RAX) == 2.0</pre><p>Yes, it works. Once we accelerate the game, the debugger stops at this breakpoint. RAX is 0x4F4E6190000, and RCX is 0x00081B1F, which sums to 0x4F4E6211B1F. I expected something closer to what we had before. We can find the constants corresponding to normal speed and pre-pausing deceleration similarly. They share the same RAX but different RCX (offsets): 0x65C0 for the normal speed, 0x81B1F for acceleration, and 0x7F3BC for deceleration.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*atgkVdvMoDbpEm82fwoYhQ.png" /><figcaption>Setting a conditional breakpoint. Screenshot by the Author.</figcaption></figure><p>Where do they come from? Let us take the address stored in RAX.</p><h3>Are these “Constants” Constant?</h3><h4>Game Acceleration State</h4><p>Initiate a memory scan. Look for the memory segments with the same value as one stored in RAX. Look for 8-byte HEX, and do not add the 0x prefix. If there are many values, return to the game, go to the menu, go to settings, and continue clicking “Next Scan” to filter out changed values. If you still have more than one value (you should not have a lot of them), add all to the address list. For each address, let us “Find out what writes to this address” (F6). One value shows thousands of writes from the following instructions:</p><pre>engine.exe+268273: 48 89 4F 18 - mov [rdi+18],rcx<br>;; ...<br>engine.exe+268677: 4C 89 6E 18 - mov [rsi+18],r13</pre><p>RDI+0x18 and RSI+0x18 contain the value in our address list. Let us scan the memory to find the value stored in RDI/RSI (the value in the address list with -0x18 offset). Many values emerge. However, we are only interested in those having a constant address. It is the engine.exe+1261BF0.</p><p>The results: engine.exe+1261BF0 points to 0x342B41F0000. In turn, 0x342B41F0000 + 0x18 points to 0x342B57A0000. It is what we need: 0x342B57A0000+0x65C0 corresponds to the normal speed constant, 0x342B57A0000+0x7F3BC to deceleration, and 0x342B57A0000+0x81B1F to acceleration. The great news is that the hierarchy holds even after the game restarts or loads a save game. The memory cell engine.exe+1261BF0 persistently points to something pointing to constants, but the address of this something and the constants changes. Let us see where the constants take their values.</p><h4>Inspecting Constants Container</h4><p>No modifications are made to the engine.exe+1261BF0 or the address it points to during the game running or save game loading. As we remember, the memory cell containing a pointer to an entity with the constants is modified extensively by the following instructions:</p><pre>engine.exe+268273: 48 89 4F 18 - mov [rdi+18],rcx<br>;; ...<br>engine.exe+268677: 4C 89 6E 18 - mov [rsi+18],r13</pre><p>The same instructions make over a hundred thousand modifications when loading a save game. We need a conditional breakpoint. During the game load, we can see that the constants are changed to meaningless values for a while and then are back again. So, there may be a moment when the current pointer points to a container that does not contain the proper constants, and it gets a new value from RCX or R13 pointing to a container with the constants. Let us write such a condition for the engine.exe+268273:</p><pre>readQword(RDI + 0x18) ~= RCX</pre><p>We have a lot of hits. The value is toggling between two values, which does not help us fetch new information. The analogous condition for the engine.exe+268677 has the same effect:</p><pre>readQword(RSI + 0x18) ~= R13</pre><h3>Conclusion and Further Directions</h3><p>We reached a stage where we will not find anything helpful without repeatedly relaunching the game, so this is the material for another debugging session described in <a href="https://medium.com/@valeriy.krygin/db4ee9ed90e3">Reverse Engineering a Videogame. Part 2. Modify the Game</a>.</p><p>This story is better ingested when you have the game and follow the described steps. Video format may be more suitable for this kind of story. I recommend you try this yourself to feel the excitement of finding something hidden inside binary code.</p><p>In <a href="https://medium.com/@valeriy.krygin/db4ee9ed90e3">Part 2</a>, I will show you how to debug the game engine initialisation to find the source of the constant I want to modify. The approach will not differ much. Nonetheless, I think it is a good guide for those willing to investigate this game&#39;s internals.</p><p>Share your opinion in the comments, in particular, about the following:</p><ul><li>What good and free reverse engineering tools do you use?</li><li>Where do you get video games that do not forbid reverse engineering and modification of their binaries?</li><li>Do you know any interesting legal nuances connected with reverse engineering in different countries?</li><li>What educational materials can you recommend for reverse engineering and patching the logic of relatively old (1990s-2000s) computer games?</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7906f9bd0e3e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dynamic Programming on Chain Graphs. Part 5: Testing]]></title>
            <link>https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-5-testing-38e0aa01f18b?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/38e0aa01f18b</guid>
            <category><![CDATA[generic-programming]]></category>
            <category><![CDATA[testing]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[c-plus-plus-language]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Wed, 01 May 2024 07:00:43 GMT</pubDate>
            <atom:updated>2024-08-01T08:31:24.587Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using <a href="https://github.com/doctest/doctest">doctest</a> for testing C++23 code and unleashing the power of X macro</h4><p>Stories of the series:</p><ul><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">Dynamic Programming on Chain Graphs. Part 1: The Problem</a>;</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">Dynamic Programming on Chain Graphs. Part 2: The Solution</a>;</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">Dynamic Programming on Chain Graphs. Part 3: Preparing for Implementation</a>;</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">Dynamic Programming on Chain Graphs. Part 4: The Implementation</a>;</li><li>Dynamic Programming on Chain Graphs. Part 5: Testing.</li></ul><p>Source code: <a href="https://github.com/definability/dynamic_programming_chain_cpp">definability/dynamic_programming_chain_cpp</a>. I license the code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it. However, the code uses the <a href="https://cimg.eu/">CImg Library</a> licensed under the terms of the <a href="http://www.cecill.info/licences/Licence_CeCILL_V2-en.html">CeCILL</a>. When you use any part of its code or any code that uses it (any file in the examples directory), read the license text carefully and follow it strictly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0_GEpW7_VpFHs7Ol5-mEnw.png" /></figure><h3>Table of Contents</h3><ul><li><a href="#39e4">Introduction</a></li><li><a href="#4d9e">The Plan</a></li><li><a href="#cfa0">Preparing for Testing</a><br>- <a href="#9c59">The Problem Class</a><br>- <a href="#0391">The Problem Chooser</a></li><li><a href="#7e4c">Test Parameters</a></li><li><a href="#18f0">Testing</a></li><li><a href="#eec2">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>Testing, whether automated or manual, is inevitable in software development. You use it for every project except the ones you do not compile/launch at all. I have never regretted spending time writing automated tests, and this project is no exception. Testing allows you to check the absence of some errors, refactor the code with more self-assurance, check the convenience of the API the code provides, and more.</p><p>This story is the final part of implementing generic dynamic programming on chain graphs for arbitrary semirings. It would be best to read <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">Dynamic Programming on Chain Graphs to understand what we test. Part 3: Preparing for Implementation</a> and <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">Dynamic Programming on Chain Graphs. Part 4: The Implementation</a> first, to know what we tested here.</p><h3>The Plan</h3><p>I want to write concise yet exhaustive tests covering edge and minimal ordinary cases.</p><p>Edge cases:</p><ol><li>Single node (no edges).</li><li>Single pair of neighbours (minimal amount of edges).</li><li>Single label.</li></ol><p>Ordinary cases:</p><ol><li>Multiple nodes with multiple labels.</li><li>Different penalty data types.</li><li>Different semirings.</li></ol><p>Also, wrong input arguments must throw validation errors.</p><p>Using different data types for penalties is easy, so we can use more than one integral and one floating point type. The behaviour of different semirings may drastically vary. Still, we have to check whether the library allows different ones to be used to ensure the absence of bias towards one of them: for example, I wrote the code with &lt;R, min, +&gt; and &lt;R, +, ×&gt; semirings in mind, so my design decisions may contain actions that prevent the library from being used with semirings like &lt;R, max, +&gt; or &lt;{0, 1}, ∨, ∧&gt;.</p><p>Remember that <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> allows you to specify extents at runtime and compile time, and <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents/rank#Example">mixing the two</a> is possible. It would be good to test these cases, too, because the code may contain some optimisations for the compile-time extents in the future, and we want to make sure they do not break the behaviour of different types of extents.</p><h3>Preparing for Testing</h3><p>I decided to use the <a href="https://github.com/doctest/doctest">doctest</a> library because it is simple, lightweight, and compatible with C++23. Its setup is <a href="https://github.com/doctest/doctest/blob/master/doc/markdown/tutorial.md#a-simple-example">simple</a>: download and include a single header file and define a DOCTEST_CONFIG_IMPLEMENT_WITH_MAINmacro.</p><p>Using <a href="https://github.com/doctest/doctest/blob/master/doc/markdown/testcases.md">fixtures</a> might be helpful. However, the author of the <a href="https://github.com/doctest/doctest">doctest</a> does <a href="https://github.com/doctest/doctest/blob/master/doc/markdown/tutorial.md#test-cases-and-subcases">not encourage</a> their use. Moreover, I said I would like to test the API convenience, so creating <a href="https://en.cppreference.com/w/cpp/language/class_template">class templates</a> to see the <a href="https://github.com/definability/dynamic_programming_chain_cpp23">definability/dynamic_programming_chain_cpp23</a> library in action is better.</p><h4>The Problem Class</h4><p>I declare the base <a href="https://en.cppreference.com/w/cpp/language/class_template">class template</a> as follows:</p><pre>template&lt;<br>  std::integral NodeIndex,<br>  std::integral LabelIndex,<br>  std::equality_comparable R,<br>  Semiring&lt;R&gt; ProblemSemiring,<br>  std::size_t nodes,<br>  std::size_t labels<br>&gt;<br>requires(nodes &gt; 0 and labels &gt; 0)<br>class DynamicProgrammingProblemBase;</pre><p>I use a <a href="https://en.cppreference.com/w/cpp/language/constraints#Concepts">concept</a> named <a href="https://en.cppreference.com/w/cpp/concepts/integral">std::integral</a> to ensure the indices can be used as template arguments of <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents">std::extents</a>. The <a href="https://en.cppreference.com/w/cpp/language/constraints#Constraints">constraints</a> for nodes and labels to be positive numbers are self-explanatory.</p><p>The <a href="https://en.cppreference.com/w/cpp/language/template_parameters">template parameters list</a> is long, and I will use it several times, so I created handy macros for this purpose:</p><pre>#define ENUMERATE_TEMPLATE_PARAMETERS(DO) \<br>  DO(std::integral, NodeIndex),           \<br>  DO(std::integral, LabelIndex),          \<br>  DO(std::equality_comparable, R),        \<br>  DO(Semiring&lt;R&gt;, ProblemSemiring),       \<br>  DO(std::size_t, nodes),                 \<br>  DO(std::size_t, labels)<br><br>#define TEMPLATE_PARAMETER(Type, value) Type value<br>#define TEMPLATE_ARGUMENT(Type, value) value<br><br>#define TEMPLATE_PARAMETER_LIST ENUMERATE_TEMPLATE_PARAMETERS(TEMPLATE_PARAMETER)<br>#define TEMPLATE_ARGUMENTS ENUMERATE_TEMPLATE_PARAMETERS(TEMPLATE_ARGUMENT)</pre><p>This idiom is called an X macro. The idea is to create a macro that enumerates a list and allows you to pass a “function” to process the items. I need this function to enumerate the <a href="https://en.cppreference.com/w/cpp/language/template_parameters">template parameters list</a> and <a href="https://en.cppreference.com/w/cpp/language/template_parameters#Template_arguments">template arguments</a> (the same list without types). This ensures consistency and avoids code duplication.</p><p>DynamicProgrammingProblemBase should allocate memory for vertices, edges, and labelling arrays because <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> only points to a memory chunk. We can use <a href="https://en.cppreference.com/w/cpp/container/array">std::array</a> because we know the sizes at compile time during testing. Remember that we test the dynamic programming algorithm and not <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a>, so the memory allocation method should not matter in our case. I define the <a href="https://en.cppreference.com/w/cpp/language/data_members">data members</a> and corresponding getters as follows:</p><pre>protected:<br>  using VerticesExtents = std::extents&lt;NodeIndex, nodes, labels&gt;;<br>  using EdgesExtents = std::extents&lt;NodeIndex, nodes - 1, labels, labels&gt;;<br><br>  std::array&lt;R, nodes * labels&gt; vertices<br>  std::array&lt;R, (nodes - 1) * labels * labels&gt; edges<br>  std::array&lt;LabelIndex, nodes&gt; labelling<br>public:<br>  Vertices&lt;R, VerticesExtents&gt; get_vertices()<br>  {<br>    return Vertices&lt;R, VerticesExtents&gt;{vertices_array.data()};<br>  }<br>  Edges&lt;R, EdgesExtents&gt; get_edges()<br>  {<br>    return Edges&lt;R, EdgesExtents&gt;{edges_array.data()};<br>  }<br>  Labelling&lt;LabelIndex, nodes&gt; get_labelling()<br>  {<br>    return Labelling&lt;LabelIndex, nodes&gt;{labelling_array.data(), nodes};<br>  }<br>  R cost;</pre><p>I create a new <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> instance every time I call the getters. Or do I not? Let us try the following <a href="https://godbolt.org/z/KM9e93hcc">example</a> on Compiler Explorer:</p><pre>#include &lt;array&gt;<br>#include &lt;iostream&gt;<br>#include &lt;mdspan&gt;<br><br>using Extents = std::extents&lt;std::size_t, 3, std::dynamic_extent, std::dynamic_extent&gt;;<br>using Wrapper = std::mdspan&lt;char, Extents&gt;;<br><br>struct MDArray<br>{<br>    auto get_data() {<br>        auto&amp;&amp; data = array.data();<br>        return Wrapper{data, 5, 2};<br>    }<br>    std::array&lt;char, 30&gt; array{};<br>};<br><br>int f(const Wrapper&amp;);<br>MDArray g();<br><br>int main()<br>{<br>    return f(g().get_data());<br>}</pre><p>Feel free to change the example source code. Once you change it, Compiler Explorer will create a copy of the code, so the link I shared here will point to the original code I posted. With a slight optimisation (even -O1), you can see the following assembly code generated from that source code (I added comments for convenience):</p><pre>push    rbx<br>sub     rsp, 64                  ;; Offset -64 from the stack top<br>lea     rbx, [rsp + 34]          ;; Put offset -64 + 34 = 30 from the stack top to RBX<br>mov     rdi, rbx<br>call    g()@PLT<br>mov     qword ptr [rsp + 8], rbx<br>mov     qword ptr [rsp + 16], 5  ;; The second extent<br>mov     qword ptr [rsp + 24], 2  ;; The third extent<br>lea     rdi, [rsp + 8]<br>call    f(std::__1::mdspan&lt;char, std::__1::extents&lt;unsigned long, 3ul, 18446744073709551615ul, 18446744073709551615ul&gt;, std::__1::layout_right, std::__1::default_accessor&lt;char&gt; &gt; const&amp;)@PLT<br>add     rsp, 64<br>pop     rbx<br>ret</pre><p>RSP contains the stack top pointer. The function uses 64 bytes (offset 64 from the stack top), and the top 30 bytes are used for the array. After the function g call, arguments are pushed to the stack — dynamic extents of the multidimensional span and, I suppose, the pointer to the data. I did not implement g and f functions so that the compiler cannot optimise them and should consider passing all the needed information between them. Even in this case, you can see that the copy constructor for <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> is not called, and the function f receives only a pointer and sizes of the span. I hope the same thing works on larger scales, particularly for my tests.</p><p>The last things to make are protected constructors and destructors. I do not want the base class explicitly used, allowing runtime polymorphism. I created the base class only to avoid code repetition for two algorithms.</p><p>The compact problem class is straightforward: inherit it from the base class and define a solve function. The fast problem class needs more members to handle the best local label array. However, it is easy as well.</p><h4>The Problem Chooser</h4><p>We have two <a href="https://en.cppreference.com/w/cpp/language/class_template">class templates</a> that can be used like follows:</p><pre>DynamicProgrammingProblemCompact&lt;TEMPLATE_ARGUMENTS&gt; compact{};<br>DynamicProgrammingProblemFast&lt;TEMPLATE_ARGUMENTS&gt; fast{};</pre><p>I want to have a convenient way to choose between these two algorithms. I could use <a href="https://en.cppreference.com/w/cpp/types/conditional">std::conditional</a>, but it will not work for <a href="https://en.cppreference.com/w/cpp/language/class_template">class templates</a>, so I implemented my <a href="https://en.cppreference.com/w/cpp/language/type_alias">alias template</a> assisted by the <a href="https://en.cppreference.com/w/cpp/language/sfinae">SFINAE</a> rule. First, I create the labels for them:</p><pre>struct AlgorithmTypes<br>{<br>  struct Fast {};<br>  struct Compact {};<br>};</pre><p>Next, I create a basic <a href="https://en.cppreference.com/w/cpp/language/class_template">class template</a> for choosing the problem, which prevents compilation by default:</p><pre>template&lt;typename Type&gt;<br>struct ProblemChooser<br>{<br>  static_assert(false, &quot;Unsupported algorithm type&quot;);<br>};</pre><p>How can this be in hand? We will use <a href="https://en.cppreference.com/w/cpp/language/partial_specialization">partial template specialisation</a>:</p><pre>template&lt;&gt;<br>struct ProblemChooser&lt;AlgorithmTypes::Fast&gt;<br>{<br>  template&lt;TEMPLATE_PARAMETER_LIST&gt;<br>  using type = DynamicProgrammingProblemFast&lt;TEMPLATE_ARGUMENTS&gt;;<br>};<br><br>template&lt;&gt;<br>struct ProblemChooser&lt;AlgorithmTypes::Compact&gt;<br>{<br>  template&lt;TEMPLATE_PARAMETER_LIST&gt;<br>  using type = DynamicProgrammingProblemCompact&lt;TEMPLATE_ARGUMENTS&gt;;<br>};</pre><p>Okay, this looks even worse than it was before. Now, we can add an <a href="https://en.cppreference.com/w/cpp/language/type_alias">alias template</a>:</p><pre>template&lt;typename Type, TEMPLATE_PARAMETER_LIST&gt;<br>using DynamicProgrammingProblem =<br>  ProblemChooser&lt;Type&gt;::template type&lt;TEMPLATE_ARGUMENTS&gt;;</pre><p>Now, we can use the needed classes like this:</p><pre>DynamicProgrammingProblem&lt;Fast, TEMPLATE_ARGUMENTS&gt; fast{};<br>DynamicProgrammingProblem&lt;Compact, TEMPLATE_ARGUMENTS&gt; compact{};</pre><p>I want to do this because <a href="https://github.com/doctest/doctest">doctest</a> allows test cases to be <a href="https://github.com/doctest/doctest/blob/master/doc/markdown/parameterized-tests.md#templated-test-cases---parameterized-by-type">parametrised by type</a>. Sure, we will require the <a href="https://en.wikipedia.org/wiki/X_macro">X macro</a> again.</p><h3>Test Parameters</h3><p>We are almost there: we have a plan, we know what to test and what tools to use. It is time to define testing parameters and write the tests.</p><p>First, I define a simple <a href="https://en.cppreference.com/w/cpp/language/class_template">class template</a> for generating semirings</p><pre>export template&lt;<br>  typename R,<br>  std::invocable&lt;const R&amp;, const R&amp;&gt; Adder = std::plus&lt;R&gt;,<br>  std::invocable&lt;const R&amp;, const R&amp;&gt; Multiplexer = std::multiplies&lt;R&gt;&gt;<br>struct SimpleSemiring<br>{<br>  Adder adder;<br>  Multiplexer multiplexer;<br>};</pre><p>and a semiring</p><pre>template&lt;typename R&gt; using MinPlusSemiring = SimpleSemiring&lt;R, Min&lt;R&gt;, Sum&lt;R&gt;&gt;;</pre><p>Next, I want to define the parameters that will vary from test to test: penalty type, algorithm, node index type, and label index type. Let us begin with an <a href="https://en.wikipedia.org/wiki/X_macro">X macro</a> for penalty types:</p><pre>#define ENUMERATE_PENALTY_TYPES(DO) \<br>  DO(signed char),                  \<br>  DO(signed short),                 \<br>  DO(signed int),                   \<br>  DO(signed long),                  \<br>  DO(float),                        \<br>  DO(double)</pre><p>Using it is simple. For example, if we wanted to alter only algorithms, we would write</p><pre>#define ENUMERATE_ALGORITHMS(T) \<br>  std::tuple&lt;T, AlgorithmTypes::Compact&gt;, \<br>  std::tuple&lt;T, AlgorithmTypes::Fast&gt;<br>#define TYPES ENUMERATE_PENALTY_TYPES(ENUMERATE_ALGORITHMS)</pre><p>The TYPES macro would contain a comma-separated enumeration of tuples forming a cartesian product of penalty and algorithm types. However, we want to go further and add the ability to use different types of nodes’ and labels’ indices. I did not find an elegant way to express a cartesian product of multiple enumerations, so I just hardcoded it:</p><pre>#define APPEND_INDEX_TYPES(...) \<br>  std::tuple&lt;__VA_ARGS__, unsigned int, signed int&gt;, \<br>  std::tuple&lt;__VA_ARGS__, signed int, signed int&gt;,   \<br>  std::tuple&lt;__VA_ARGS__, unsigned int, unsigned int&gt;, \<br>  std::tuple&lt;__VA_ARGS__, signed int, unsigned int&gt;</pre><p><a href="https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html">__VA_ARGS__</a> is a macro for <a href="https://en.cppreference.com/w/cpp/preprocessor/replace#Function-like_macros">variable arguments</a>. The preprocessor replaces it with all the arguments of APPEND_INDEX_TYPES, preserving comma-separation. Next, I modify the aforementioned macro a bit and get</p><pre>#define ENUMERATE_ALGORITHMS(T) \<br>  APPEND_INDEX_TYPES(T, AlgorithmTypes::Compact), \<br>  APPEND_INDEX_TYPES(T, AlgorithmTypes::Fast)<br>#define TYPES ENUMERATE_PENALTY_TYPES(ENUMERATE_ALGORITHMS)</pre><p>I created a convenient way to convert such tuples to problems using an <a href="https://en.cppreference.com/w/cpp/language/type_alias">alias template</a> as I did before:</p><pre>template&lt;typename TypesTuple, std::size_t nodes, std::size_t labels&gt; struct ProblemFromTupleHelper<br>{<br>  using R = std::tuple_element_t&lt;0, TypesTuple&gt;;<br>  using Algorithm = std::tuple_element_t&lt;1, TypesTuple&gt;;<br>  using NodeIndex = std::tuple_element_t&lt;2, TypesTuple&gt;;<br>  using LabelIndex = std::tuple_element_t&lt;3, TypesTuple&gt;;<br><br>  using Problem = DynamicProgrammingProblem&lt;Algorithm, NodeIndex, LabelIndex, R, MinPlusSemiring&lt;R&gt;, nodes, labels&gt;;<br>};<br><br>template&lt;typename TypesTuple, std::size_t nodes, std::size_t labels&gt;<br>using ProblemFromTuple = ProblemFromTupleHelper&lt;TypesTuple, nodes, labels&gt;::Problem;</pre><h3>Testing</h3><p>Let us look at a simple test:</p><pre>TEST_CASE_TEMPLATE(&quot;one node and one label&quot;, TypesTuple, TYPES)<br>{<br>  ProblemFromTuple&lt;TypesTuple, 1, 1&gt; problem;<br>  problem.get_vertices()[0u, 0u] = 0;<br>  problem.solve();<br><br>  CHECK_EQ(problem.cost, 0);<br>  CHECK_EQ(problem.get_vertices()[0u, 0u], 0);<br>  CHECK_EQ(problem.get_labelling()[0u], 0);<br>}</pre><p>I use a <a href="https://github.com/doctest/doctest/blob/master/doc/markdown/parameterized-tests.md#templated-test-cases---parameterized-by-type">templated test case</a> and want the parameter name to be TypesTuple. Then, I provide the list of possible TypesTuple in TYPES macro defined before. Each item is an <a href="https://en.cppreference.com/w/cpp/utility/tuple">std::tuple</a> <a href="https://en.cppreference.com/w/cpp/language/template_specialization">template specialisation</a>. I use <a href="https://en.cppreference.com/w/cpp/utility/tuple_element">std::tuple_element_t</a> to fetch a type from the tuple.</p><p>You may protest against an ordinary equality comparison of floating point values and advocate using <a href="https://en.cppreference.com/w/cpp/types/numeric_limits/epsilon">std::numeric_limits&lt;R&gt;::epsilon</a>. Nevertheless, it must be fine if the compiler follows <a href="https://en.wikipedia.org/wiki/IEEE_754">IEEE 754</a> for floating-point numbers. So, it is a good thing to check <a href="https://en.cppreference.com/w/cpp/types/numeric_limits/is_iec559">std::numeric_limits&lt;T&gt;::is_iec559</a> with <a href="https://en.cppreference.com/w/cpp/language/static_assert">static_assert</a>:</p><pre>static_assert(<br>  std::numeric_limits&lt;R&gt;::is_iec559<br>  or not std::is_floating_point_v&lt;R&gt;);</pre><p>I use <a href="https://en.cppreference.com/w/cpp/language/operator_alternative#Alternative_tokens">alternative tokens</a>. I do not like &amp;&amp;, ||, and !. Writing and, or, and not instead feels better.</p><p>The rest is trivial: cover the cases that need to be covered. More diverse tests help uncover caveats in your design decisions and programming flaws.</p><h3>Conclusion and Further Directions</h3><p>Implementing dynamic programming on chain graphs for an arbitrary semiring is complete. We began with <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">the problem</a>, found its <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">solution</a>, designed the library <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">interface</a>, <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb">implemented</a> it, and <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-5-testing-38e0aa01f18b">tested</a> the result. Now, we can use this library: We are sure it works in the cases we consider important, and it has a convenient API — its examples of use can be peeked at from the tests. What else do we need? We need a homework:</p><ul><li>Apply the algorithm to some real problems — <a href="https://medium.com/@valeriy.krygin/scanline-stereo-vision-85ff252ec521">stereo vision</a>, <a href="https://medium.com/@valeriy.krygin/binary-image-denoising-with-the-boost-graph-max-flow-6ec817d62858">image denoising</a>, finding the shortest path, finding the expected value of a Hidden Markov Model, etc.</li><li>Check test coverage and enrich them with missing parts.</li><li>Consider and cover noteworthy cases that are not covered by the tests.</li><li>Think about more elegant templates and macros for generalisation of the tests.</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=38e0aa01f18b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dynamic Programming on Chain Graphs. Part 4: The Implementation]]></title>
            <link>https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-4-the-implementation-35b55a528afb?source=rss-f7c029f045f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/35b55a528afb</guid>
            <category><![CDATA[graph-algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[c-plus-plus-language]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[generic-programming]]></category>
            <dc:creator><![CDATA[Valeriy Krygin]]></dc:creator>
            <pubDate>Sat, 13 Apr 2024 11:23:56 GMT</pubDate>
            <atom:updated>2024-08-01T08:31:21.006Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using modern C++ features to implement dynamic programming on chain graphs on an arbitrary semiring</h4><p>Stories of the series:</p><ul><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">Dynamic Programming on Chain Graphs. Part 1: The Problem</a>;</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">Dynamic Programming on Chain Graphs. Part 2: The Solution</a>;</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">Dynamic Programming on Chain Graphs. Part 3: Preparing for Implementation</a>;</li><li>Dynamic Programming on Chain Graphs. Part 4: The Implementation.</li><li><a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-5-testing-38e0aa01f18b">Dynamic Programming on Chain Graphs. Part 5: Testing</a>.</li></ul><p>Source code: <a href="https://github.com/definability/dynamic_programming_chain_cpp">definability/dynamic_programming_chain_cpp</a>. I license the code under the <a href="https://choosealicense.com/licenses/mit/">MIT license</a> so you can use it, spread it, and modify it. However, the code uses the <a href="https://cimg.eu/">CImg Library</a> licensed under the terms of the <a href="http://www.cecill.info/licences/Licence_CeCILL_V2-en.html">CeCILL</a>. When you use any part of its code or any code that uses it (any file in the examples directory), read the license text carefully and follow it strictly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*65vzAdoWZ1aDYanEg0AhHQ.png" /></figure><h3>Table of Contents</h3><ul><li><a href="#bdca">Introduction</a></li><li><a href="#3b67">Why are Modules Important?</a></li><li><a href="#39f5">Repeating the Algorithm</a></li><li><a href="#435b">The Function Template Declaration</a></li><li><a href="#41ec">Cost Calculation Function Declaration</a><br>- <a href="#275e">Forwarding References</a><br>- <a href="#4ab9">Polishing Semiring</a></li><li><a href="#bcce">Cost Calculation Function Definition</a><br>- <a href="#d23a">Multidimensional Span Slicing</a><br>- <a href="#2ad4">Inner Product</a><br>- <a href="#f9f0">The Function Body</a></li><li><a href="#a6eb">Conclusion and Further Directions</a></li></ul><h3>Introduction</h3><p>This page aims to show you some features of modern C++. The special guests are C++20 <a href="https://en.cppreference.com/w/cpp/language/modules">modules</a> that allow replacing <a href="https://en.cppreference.com/w/cpp/preprocessor/include">#include</a> with <a href="https://en.cppreference.com/w/cpp/language/modules#Importing_modules_and_header_units">import</a> and making code cleaner. To keep the writing short, I do not describe them deeply, so let me know if you want me to do this in another story. Another interesting entity is <a href="https://en.cppreference.com/w/cpp/language/auto">auto</a> — a keyword that obtained a new meaning in C++11 and lets you forget about types in some sense, almost like var and val in Kotlin and JavaScript and let in JS and Rust, mainly when you use auto&amp;&amp;, a so-called <a href="https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers">universal reverence</a> or <a href="https://en.cppreference.com/w/cpp/language/reference#Forwarding_references">forwarding reference</a>. Be careful, and don’t confuse it with an <a href="http://thbecker.net/articles/rvalue_references/section_01.html">rvalue reference</a>. If you are curious about <a href="https://en.cppreference.com/w/cpp/language/crtp">CRTP</a>, you may be delighted by <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0847r7.html">deducing this</a>.</p><p>This story is a continuation of <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-3-preparing-for-implementation-bdceb5bf1345">Dynamic Programming on Chain Graphs. Part 3: Preparing for Implementation</a>, which you must read first to understand what happens here. If you want to know more, begin with <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257">Dynamic Programming on Chain Graphs. Part 1: The Problem</a> to find out what the task is, or at least <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e">Dynamic Programming on Chain Graphs. Part 2: The Solution</a>, which contains the algorithm implemented here.</p><p>Note that currently (April 2024), g++, clang++, and MSVC shipped with stable releases of popular operating systems do not support some features I will show you. That is why I use Docker with LLVM 18 on board. <a href="https://cmake.org/cmake/help/latest/release/3.28.html">CMake 3.28</a> (build system), <a href="https://ninja-build.org/">Ninja</a> of version <a href="https://github.com/ninja-build/ninja/releases/tag/v1.10.0">1.10</a> or higher, <a href="https://releases.llvm.org/18.1.0/tools/clang/docs/ReleaseNotes.html">Clang 18</a> (C/C++ compiler), and <a href="https://releases.llvm.org/18.1.0/projects/libcxx/docs/ReleaseNotes.html">libc++ 18</a> (C++ standard library implementation by LLVM) are the main elements.</p><h3>Why are Modules Important?</h3><p>In short, C++20 <a href="https://en.cppreference.com/w/cpp/language/modules">modules</a> provide a more familiar behaviour for those who use other programming languages like <a href="https://docs.python.org/3.10/reference/import.html">Python</a>, <a href="https://kotlinlang.org/docs/packages.html#imports">Kotlin</a>, etc. The <a href="https://en.cppreference.com/w/cpp/language/modules#Importing_modules_and_header_units">import</a> behaviour is not as straightforward as one of <a href="https://en.cppreference.com/w/cpp/preprocessor/include">#include</a>, but in theory, <a href="https://en.cppreference.com/w/cpp/language/modules#Importing_modules_and_header_units">import</a> is faster and leaves you fewer chances to mess things up. To learn more about the requirements of this feature, read the official blog post <a href="https://www.kitware.com/import-cmake-the-experiment-is-over/">import CMake; the Experiment is Over!</a></p><p>Visually, <a href="https://en.cppreference.com/w/cpp/language/modules#Importing_modules_and_header_units">import</a> in C++ allows you to import entities from a module marked with an <a href="https://en.cppreference.com/w/cpp/language/modules#Exporting_declarations_and_definitions">export</a> keyword, like in ES6. This property implies that the users importing your module cannot use what you do not explicitly allow, giving unexported parts a <a href="https://en.cppreference.com/w/cpp/language/storage_duration#Module_linkage">module linkage</a>.</p><p>The brilliant part about the modules is that they allow the compiler to avoid recompiling the same things repeatedly when building a project, thus reducing the compilation time. Previously, changing a file executed recompilation of all the code it included. With modules, a compiler may need to recompile the file and link the precompiled modules to it.</p><h3>Repeating the Algorithm</h3><p>The <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-1-the-problem-78bcf0250257#f2df">problem input</a> is</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fm6GEacaRgVkrmdpiHevULr&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fm6GEacaRgVkrmdpiHevULr&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="200" height="345" frameborder="0" scrolling="no"><a href="https://medium.com/media/eaa65606d18a32ace274a9d71a16d10b/href">https://medium.com/media/eaa65606d18a32ace274a9d71a16d10b/href</a></iframe><p>The <a href="https://medium.com/@valeriy.krygin/dynamic-programming-on-chain-graphs-part-2-the-solution-37c1bad8570e#3b00">memory-efficient algorithm</a> of solving the labelling problem on a chain graph for an arbitrary semiring is</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2Fht6TJLuuxb5d8314D5gyqN&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2Fht6TJLuuxb5d8314D5gyqN&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="575" height="248" frameborder="0" scrolling="no"><a href="https://medium.com/media/3bbe99ee2a5bd5564ecd51d94e536454/href">https://medium.com/media/3bbe99ee2a5bd5564ecd51d94e536454/href</a></iframe><p>I will not use recursion in my code. You may use it with a <a href="https://en.wikipedia.org/wiki/Tail_call">tail call</a> to avoid stack overflow and see what happens.</p><h3>The Function Template Declaration</h3><p>We stopped at the <a href="https://en.cppreference.com/w/cpp/language/function">declaration</a> with handy <a href="https://en.cppreference.com/w/cpp/language/type_alias">alias templates</a> and a <a href="https://en.cppreference.com/w/cpp/language/constraints">concept</a>:</p><pre><br>#include &lt;concepts&gt;<br>#include &lt;mdspan&gt;<br>#include &lt;span&gt;<br><br>template&lt;class SpecificSemiring, typename R&gt; concept Semiring =<br>requires(SpecificSemiring semiring, R&amp; lhs, R&amp; rhs)<br>{<br>  { semiring.adder(lhs, rhs) } -&gt; std::same_as&lt;R&gt;;<br>  { semiring.multiplexer(lhs, rhs) } -&gt; std::same_as&lt;R&gt;;<br>};<br><br>template&lt;typename R, typename Extents&gt; requires(Extents::rank() == 2)<br>  using Vertices = std::mdspan&lt;R, Extents&gt;;<br>template&lt;typename R, typename Extents&gt; requires(Extents::rank() == 3)<br>  using Edges = std::mdspan&lt;R, Extents&gt;;<br>template&lt;typename Label, std::size_t extent = std::dynamic_extent&gt;<br>  using Labelling = std::span&lt;Label, extent&gt;;<br><br>template&lt;<br>  std::equality_comparable R,<br>  Semiring&lt;R&gt; SpecificSemiring,<br>  typename VerticesExtents,<br>  typename EdgesExtents,<br>  typename Label,<br>  std::size_t labelling_extent<br>&gt;<br>void dynamic_programming_compact(<br>  SpecificSemiring semiring,<br>  const Vertices&lt;R, VerticesExtents&gt;&amp; vertices,<br>  const Edges&lt;R, EdgesExtents&gt;&amp; edges,<br>  const Labelling&lt;Label, labelling_extent&gt;&amp; labelling,<br>  R&amp; labelling_cost<br>);</pre><p>I still have to use <a href="https://en.cppreference.com/w/cpp/preprocessor/include">#include</a> here because <a href="https://releases.llvm.org/18.1.0/projects/libcxx/docs/ReleaseNotes.html">libc++ 18</a> still does not support <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2465r3.pdf">Standard Library Modules std and std.compat</a>. MSVC 19.36 seems to contain them. However, MSVC 19.36 does not support a <a href="https://en.cppreference.com/w/cpp/language/operators#Array_subscript_operator">multidimensional subscript operator</a>, so I decided to choose <a href="https://releases.llvm.org/18.1.0/tools/clang/docs/ReleaseNotes.html">Clang 18</a> with <a href="https://releases.llvm.org/18.1.0/projects/libcxx/docs/ReleaseNotes.html">libc++ 18</a> and live without import std for a while. There are also a lot of other <a href="https://en.cppreference.com/w/cpp/compiler_support/23">C++23 features</a> supported by <a href="https://releases.llvm.org/18.1.0/tools/clang/docs/ReleaseNotes.html">Clang 18</a> and not supported by MSVC.</p><p>I decomposed the code into three main parts: input validation, cost calculation, and labelling calculation:</p><pre>template&lt;/* template arguments */&gt;<br>void dynamic_programming_compact(/* function arguments */)<br>{<br>  validate_input(vertices, edges, labelling);<br>  labelling_cost = calculate_cost(semiring, vertices, edges);<br>  calculate_labelling(semiring, vertices, edges, labelling, labelling_cost);<br>}</pre><p>The input validation is a series of trivial <a href="https://en.cppreference.com/w/cpp/language/if">ifs</a> and <a href="https://en.cppreference.com/w/cpp/language/throw">throws</a>, so I will not stop there. The other two functions are interesting from the perspective of C++ features.</p><h3>Cost Calculation Function Declaration</h3><p>I decided to go with the following prototype of the function for the cost calculation:</p><pre>auto calculate_cost(auto&amp;&amp; semiring, auto&amp;&amp; vertices, auto&amp;&amp; edges);</pre><h4>Forwarding References</h4><p>What are these auto&amp;&amp;, and why do I use auto without ampersand as the function return type? Let me rewrite this as a <a href="https://en.cppreference.com/w/cpp/language/function_template">function template</a> explicitly</p><pre>template&lt;typename R, typename S, typename V, typename E&gt;<br>R calculate_cost(S&amp;&amp; semiring, V&amp;&amp; vertices, E&amp;&amp; edges);</pre><p>These S&amp;&amp;, V&amp;&amp;, and E&amp;&amp; are not <a href="http://thbecker.net/articles/rvalue_references/section_01.html">rvalue references</a> but <a href="https://en.cppreference.com/w/cpp/language/reference#Forwarding_references">forwarding references</a>, also known as <a href="https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers">universal reverence</a>. Simply put, this is a special notation for template arguments, which can be transformed into an <a href="https://en.cppreference.com/w/cpp/language/reference#Lvalue_references">lvalue reference</a>, a <a href="https://en.cppreference.com/w/cpp/language/reference#Lvalue_references">constant lvalue reference</a>, an <a href="http://thbecker.net/articles/rvalue_references/section_01.html">rvalue reference</a>, or even a <a href="http://thbecker.net/articles/rvalue_references/section_01.html">const rvalue reference</a>, depending on what arguments you provide to the function. Check out <a href="https://godbolt.org/z/7ejq3Eq8e">this example</a> on Compiler Explorer to see it yourself. You can choose different compilers and experiment with flags. These actions will not affect the code attached to this page because you will work with your copy of the code.</p><p>If you are unsure which reference type to choose for a variable or a function argument, you can use auto&amp;&amp;. Nonetheless, things are different with the function output. To be lazy and safe, use <a href="https://en.cppreference.com/w/cpp/language/auto">decltype(auto)</a>. If you use auto&amp;&amp; as the function return type, you may return an <a href="https://en.cppreference.com/w/cpp/language/reference#Lvalue_references">lvalue reference</a> to a temporary variable, ending up with a <a href="https://en.cppreference.com/w/cpp/language/reference#Dangling_references">dangling reference</a>. The calculate_cost function returns a labelling cost value, so I use an ordinary <a href="https://en.cppreference.com/w/cpp/language/auto">auto</a> here. Also, remember that using an ordinary <a href="https://en.cppreference.com/w/cpp/language/auto">auto</a> for arguments makes them ordinary values, which forces the passing of the arguments by value rather than by reference.</p><h4>Polishing Semiring</h4><p>Take a closer look at this formula fragment</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FrNU7cZz8Tos7k5GpL9hS5P&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FrNU7cZz8Tos7k5GpL9hS5P&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="385" height="160" frameborder="0" scrolling="no"><a href="https://medium.com/media/e1e2c1ffdafbc1c3e0e51fc3515b124c/href">https://medium.com/media/e1e2c1ffdafbc1c3e0e51fc3515b124c/href</a></iframe><p>Remember that we can override elements of 𝜑 instead of using a separate 𝜃. In this case, the formula can be transformed into a mix of mathematics and C++:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2F2kaGEmQ8E6hisd7DvxWFG7&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2F2kaGEmQ8E6hisd7DvxWFG7&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="337" height="160" frameborder="0" scrolling="no"><a href="https://medium.com/media/febd82105ddf08f37de972e7ec14d00c/href">https://medium.com/media/febd82105ddf08f37de972e7ec14d00c/href</a></iframe><p>It becomes evident that our semiring needs an in-place multiplication to stay efficient if R is not an ordinary number. Furthermore, I want this in-place multiplexer to accept an <a href="https://en.cppreference.com/w/cpp/language/reference#Rvalue_references">rvalue reference</a> to have the ability to do whatever is needed to make the operation efficient:</p><pre>export template&lt;class SpecificSemiring, typename R&gt; concept Semiring =<br>requires(SpecificSemiring semiring, R&amp; lhs, R&amp; rhs)<br>{<br>  { semiring.adder(lhs, rhs) } -&gt; std::same_as&lt;R&gt;;<br>  { semiring.multiplexer(lhs, rhs) } -&gt; std::same_as&lt;R&gt;;<br>}<br>and requires(SpecificSemiring semiring, R&amp; result, R&amp;&amp; multiplier)<br>{<br>  {<br>  semiring.multiplexer.inplace(result, std::move(multiplier))<br>  } -&gt; std::same_as&lt;void&gt;;<br>};</pre><p>Now, we must add this inplace member to multiplexers. Let us return to</p><pre>template&lt;typename R&gt;<br>struct Min<br>{<br>  static R operator()(const R&amp; lhs, const R&amp; rhs)<br>  {<br>    return std::min(lhs, rhs);<br>  }<br>};</pre><p>We can implement a <a href="https://en.cppreference.com/w/cpp/language/static#Static_member_functions">static member function</a> inplace:</p><pre>template&lt;typename R&gt;<br>struct Min<br>{<br>  static R operator()(const R&amp; lhs, const R&amp; rhs)<br>  {<br>    return std::min(lhs, rhs);<br>  }<br>  static void inplace(R&amp; result, R&amp;&amp; operand)<br>  {<br>    result = (*this)(result, std::move(operand));<br>  }<br>};</pre><p>This approach would need copy-paste for all new operations that do not have native in-place analogues. We can use <a href="https://en.cppreference.com/w/cpp/language/virtual">virtual member functions</a> and inherit from them like</p><pre>template&lt;typename R&gt; struct AbstractOperation<br>{<br>  virtual R operator()(const R&amp; lhs, const R&amp; rhs) = 0;<br>  void inplace(R&amp; result, R&amp;&amp; operand)<br>  {<br>    result = (*this)(result, std::move(operand));<br>  }<br>};<br><br>template&lt;typename R&gt; struct Min: AbstractOperation&lt;R&gt;<br>{<br>  R operator()(const R&amp; lhs, const R&amp; rhs) override<br>  {<br>    return std::min(lhs, rhs);<br>  }<br>};</pre><p>I do not like this approach. In an older C++ version, I would use the <a href="https://en.cppreference.com/w/cpp/language/crtp">Curiously Recurring Template Pattern</a>. With C++23 at hand, I use an <a href="https://en.cppreference.com/w/cpp/language/member_functions#Explicit_object_member_functions">explicit object member function</a>, also known as <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0847r7.html">deducing this</a>. The idea is simple: I say that the function must call members belonging to the currently used <a href="https://en.cppreference.com/w/cpp/language/this">this</a>. Theoretically, this approach is faster than <a href="https://en.cppreference.com/w/cpp/language/virtual">virtual member functions</a> because the right function choice is made during the compilation time. However, there are cases when it is more convenient to use <a href="https://en.cppreference.com/w/cpp/language/virtual">virtual member functions</a>. Those who worked with <a href="https://docs.python.org/3.10/tutorial/classes.html">Python classes</a> may find this syntax familiar:</p><pre>template&lt;typename R&gt; struct FakeInplaceOperation<br>{<br>  void inplace(this auto&amp;&amp; self, R&amp; result, R&amp;&amp; operand)<br>  {<br>    result = self(result, std::move(operand));<br>  }<br>};<br><br>template&lt;typename R&gt; struct Max: FakeInplaceOperation&lt;R&gt;<br>{<br>  static R operator()(const R&amp; lhs, const R&amp; rhs)<br>  {<br>    return std::max(lhs, rhs);<br>  }<br>};</pre><h3>Cost Calculation Function Definition</h3><h4>Multidimensional Span Slicing</h4><p>The algorithm traverses the chain from its end, so we must obtain the last element. Assuming the number of nodes is greater than zero (and checking it in validate_input), we can get a slice containing penalties of all labels in the last node:</p><pre>auto&amp;&amp; next_node_vertices = get_slice(vertices, vertices.extent(0) - 1);</pre><p>In the future, we can use <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2630r4.html">submdspan</a> to get a part of the <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> instance. If you are familiar with MatLab, NumPy, or modern Fortran, you have probably encountered code like array[i, :] or array(i, :) that gets the row i (or column in the case of Fortran ordering) of a matrix. An analogue of such a feature will also be available in C++ for <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a>. Currently, we have to use custom implementations. Another complication is the lack of documentation of <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> features on <a href="https://cppreference.com/">cppreference.com</a>, so I had to rely on the <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0009r18.html">official proposal</a>.</p><p>We need a function that constructs the <a href="https://en.cppreference.com/w/cpp/container/span">std::span</a> instance from the elements of the last dimension of the input <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> instance. This requires knowing the pointer to the first element of the slice and the number of elements in the slice. We can sketch the function:</p><pre>auto get_slice(auto&amp;&amp; two_dimensional_span, auto&amp;&amp; row)<br>{<br>  return std::span{<br>    get_first_element_pointer(two_dimensional_span, row),<br>    get_columns_number(two_dimensional_span),<br>  };<br>}</pre><p>The number of columns is straightforward with the <a href="https://en.cppreference.com/w/cpp/container/mdspan#Example">std::mdspan::extent</a> member function. Getting the pointer to the first element may be split into two parts: get the pointer that two_dimensional_span owns and add the offset of the needed row. The member function <a href="https://en.cppreference.com/w/cpp/container/mdspan/data_handle">std::mdspan::data_handle</a> provides the pointer, while <a href="https://en.cppreference.com/w/cpp/container/mdspan/mapping">std::mdspan::mapping</a> offers an object that turns multidimensional indices into a single-dimensional index. We do not need to worry about pointer arithmetic: <a href="https://en.cppreference.com/w/cpp/container/mdspan/accessor">std::mdspan::accessor</a> member function provides an object that can create a needed pointer based on the data handle and offset.</p><pre>auto get_slice(auto&amp;&amp; two_dimensional_span, auto&amp;&amp; row)<br>{<br>  auto&amp;&amp; begin = two_dimensional_span.data_handle();<br>  auto&amp;&amp; offset = two_dimensional_span.mapping()(row, 0);<br>  auto&amp;&amp; accessor = two_dimensional_span.accessor();<br>  <br>  auto&amp;&amp; row_begin = accessor.offset(begin, offset);<br>  <br>  auto&amp;&amp; colums_number = two_dimensional_span.extent(1);<br>  return std::span{row_begin, columns_number};<br>}</pre><p>Were you scared of pointers? <a href="https://www.imdb.com/title/tt1411250/quotes/?item=qt2112492">Maybe you’re all scared of the wrong thing</a>.</p><p>We will also need slicing for three-dimensional spans. Should we duplicate the same function? No, we can use a <a href="https://en.cppreference.com/w/cpp/language/parameter_pack">template parameter pack</a>. Just imagine the effort needed to implement <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a> containing <a href="https://en.cppreference.com/w/cpp/language/template_specialization">specialisations</a> for all possible dimensions. The behaviour of the <a href="https://en.cppreference.com/w/cpp/language/parameter_pack">parameter pack</a> in the <a href="https://en.cppreference.com/w/cpp/language/function_template">function template</a> is similar to <a href="https://en.cppreference.com/w/cpp/language/variadic_arguments">variadic arguments</a> in <a href="https://en.cppreference.com/w/cpp/utility/variadic">variadic functions</a> (remember the <a href="https://en.cppreference.com/w/c/io/fprintf">printf</a> function from C), but the <a href="https://en.cppreference.com/w/cpp/language/parameter_pack">template parameter pack</a> is safer. The syntax is simple — just place an ellipsis (…, like “and so on”) before the argument you want to contain an arbitrary number of values. Put an ellipsis after its name to pass this parameter pack to another function as separate parameters. You are now ready to comprehend the generic function for getting the last slice of a multidimensional span:</p><pre>auto get_slice(auto&amp;&amp; input_span, auto&amp;&amp;... indices)<br>{<br>  auto&amp;&amp; begin = input_span.data_handle();<br>  auto&amp;&amp; offset = input_span.mapping()(indices..., 0);<br>  auto&amp;&amp; accessor = input_span.accessor();<br>  <br>  auto&amp;&amp; slice_begin = accessor.offset(begin, offset);<br>  <br>  auto&amp;&amp; slice_size = input_span.extent(sizeof...(indices));<br>  return std::span{slice_begin, slice_size};<br>}</pre><p>The <a href="https://en.cppreference.com/w/cpp/language/sizeof...">sizeof… operator</a> obtains the number of elements in a <a href="https://en.cppreference.com/w/cpp/language/parameter_pack">parameter pack</a>. How can we be sure that the user provides two indices for three-dimensional arrays and one for two-dimensional arrays? We can add a <a href="https://en.cppreference.com/w/cpp/language/constraints#Requires_clauses">requires clause</a>:</p><pre>requires(<br>  sizeof...(indices)<br>  == std::decay_t&lt;decltype(input_span)&gt;::extents_type::rank() - 1<br>)</pre><p>I decided to rely on checks provided by <a href="https://en.cppreference.com/w/cpp/container/mdspan#Member_types">std::mdspan::mapping_type</a>, which will fail compilation when get_slice is called with an incorrect number of indices. Check it yourself in <a href="https://godbolt.org/z/q1zYvbvbj">the example</a> I hosted for you on Compiler Explorer. Besides, get_slice is not a public function of our module, so it is designated solely for the library developers, who must understand what they do. Moreover, in the future, it will hopefully be replaced by <a href="https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2630r4.html">submdspan</a>.</p><p>Somebody may be concerned about using 0 in input_span.mapping()(indices…, 0);. It should be castable to <a href="https://en.cppreference.com/w/cpp/container/mdspan#Member_types">std::mdspan::size_type</a>, which the user can specify. However, <a href="https://en.cppreference.com/w/cpp/container/mdspan#Member_types">std::mdspan::extents_type</a> must be a specialisation of <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents">std::extents</a>, <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents#Member_types">std::extents::index_type</a> must be a signed or unsigned integer type, and <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents#Member_types">std::extents::size_type</a> is <a href="http://en.cppreference.com/w/cpp/types/make_unsigned">std::make_unsigned_t</a>&lt;<a href="https://en.cppreference.com/w/cpp/container/mdspan/extents#Member_types">std::extents::index_type</a>&gt;. Thus, if <a href="https://en.cppreference.com/w/cpp/container/mdspan/extents#Member_types">std::extents::index_type</a> does not fit the requirement, the program is <a href="https://en.cppreference.com/w/cpp/language/ub#Explanation">ill-formed</a>, which is not the same as <a href="https://en.cppreference.com/w/cpp/language/ub#Explanation">undefined behaviour</a>.</p><h4>Inner Product</h4><p>The formula</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fmath.embed.fun%2Fembed%2FnfrpKnRHaaAF4Hk1HvxCpm&amp;display_name=Embed+Fun&amp;url=https%3A%2F%2Fmath.embed.fun%2FnfrpKnRHaaAF4Hk1HvxCpm&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=embed" width="345" height="160" frameborder="0" scrolling="no"><a href="https://medium.com/media/17faa1a9d3f67a3fe6341df78e2691ba/href">https://medium.com/media/17faa1a9d3f67a3fe6341df78e2691ba/href</a></iframe><p>holds one more gem. The right-hand side of the expression looks like a <a href="https://en.wikipedia.org/wiki/Dot_product#Coordinate_definition">dot product</a> — a sum of products of corresponding elements of two arrays. STL contains a function <a href="https://en.cppreference.com/w/cpp/algorithm/inner_product">std::inner_product</a> that exactly does such things on arbitrary semirings! C++17 enriched STL with <a href="https://en.cppreference.com/w/cpp/algorithm/transform_reduce">std::transform_reduce</a>, designed for semirings with commutative addition, where the order of summands does not matter. As with other algorithms, this relies on iterators. Let me write a wrapper for convenience</p><pre>auto inner_product(<br>  auto&amp;&amp; semiring,<br>  auto&amp;&amp; current_label_edges,<br>  auto&amp;&amp; next_node_vertices<br>)<br>{<br>  [[assume(next_node_vertices.begin() != next_node_vertices.end()]]<br>  [[assume(current_label_edges.begin() != current_label_edges.end()]]<br>  return std::transform_reduce(<br>    ++next_node_vertices.begin(),<br>    next_node_vertices.end(),<br>    ++current_label_edges.begin(),<br>    semiring.multiplexer(next_node_vertices[0], current_label_edges[0]),<br>    semiring.adder,<br>    semiring.multiplexer<br>  );<br>}</pre><p>The <a href="https://en.cppreference.com/w/cpp/algorithm/transform_reduce">std::transform_reduce</a> requires the beginning and end iterators and the initial value to return when the input containers are empty, which is why the code contains multiple increments of iterators. The <a href="https://en.cppreference.com/w/cpp/language/attributes/assume">assume attribute</a> is yet another C++23 feature. It signals the compiler developer’s assumptions about the code. If an assumption is not true, the <a href="https://en.cppreference.com/w/cpp/language/ub">behaviour is undefined</a>. In our case, the assumption is that the input spans are not empty.</p><h4>The Function Body</h4><p>Putting all these things together, we get the cost calculation function. I hope everything is clear now.</p><pre>auto calculate_cost(auto&amp;&amp; semiring, auto&amp;&amp; vertices, auto&amp;&amp; edges)<br>{<br>  using Size = std::decay_t&lt;decltype(vertices)&gt;::extents_type::size_type;<br><br>  [[assume(vertices.extent(0) &gt;= 1)]]<br>  auto next_node = vertices.extent(0) - Size{1};<br>  auto&amp;&amp; next_node_vertices = get_slice(vertices, next_node);<br>  for (; next_node &gt; 0; --next_node)<br>  {<br>    [[assume(next_node &gt;= 1)]]<br>    const auto current_node = next_node - Size{1};<br>    auto&amp;&amp; current_node_vertices = get_slice(vertices, current_node);<br><br>    for (auto label = Size{0}; label &lt; vertices.extent(1); ++label)<br>    {<br>      auto&amp;&amp; current_label_edges = get_slice(edges, current_node, label);<br>      auto&amp;&amp; inner_product_result = inner_product(<br>        semiring,<br>        current_label_edges,<br>        next_node_vertices<br>      );<br>      semiring.multiplexer.inplace(<br>        current_node_vertices[label],<br>        std::move(inner_product_result));<br>    }<br>    next_node_vertices = current_node_vertices;<br>  }<br><br>  [[assume(next_node_vertices.begin() != next_node_vertices.end())]]<br>  return std::reduce(<br>    ++next_node_vertices.begin(),<br>    next_node_vertices.end(),<br>    *next_node_vertices.begin(),<br>    semiring.adder<br>  );<br>}</pre><h3>Conclusion and Further Directions</h3><p>We went through several interesting features of modern C++: <a href="https://en.cppreference.com/w/cpp/language/reference#Forwarding_references">forwarding references</a> (a.k.a. <a href="https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers">universal reverence</a>), members of <a href="https://en.cppreference.com/w/cpp/container/mdspan">std::mdspan</a>, <a href="https://en.cppreference.com/w/cpp/language/parameter_pack">template parameter pack</a>, <a href="https://en.cppreference.com/w/cpp/language/reference#Rvalue_references">rvalue reference</a>, <a href="https://en.cppreference.com/w/cpp/language/member_functions#Explicit_object_member_functions">explicit object member function</a>, <a href="https://en.cppreference.com/w/cpp/algorithm/transform_reduce">std::transform_reduce</a>, and other things. Some parts are more straightforward, and some are more sophisticated, so I hope to receive your opinion to shape future stories and edit this one according to my readers’ needs.</p><p>Other code uses similar features, so I do not cover it on this page and leave it for you to explore. Here are other tasks you can think about:</p><ul><li>Try to refactor calculate_cost to rely less on indices and more on iterators and STL algorithms.</li><li>Apply the algorithm to some real problems — <a href="https://medium.com/@valeriy.krygin/scanline-stereo-vision-85ff252ec521">stereo vision</a>, <a href="https://medium.com/@valeriy.krygin/binary-image-denoising-with-the-boost-graph-max-flow-6ec817d62858">image denoising</a>, finding the shortest path, finding the expected value of a Hidden Markov Model, etc.</li><li>Rewrite the code in C++17 and compare the compilation time to understand whether it benefits from modules. Remember to use a compiler that does not support <a href="https://en.cppreference.com/w/cpp/language/modules">C++20 modules</a> to avoid optimising template compilation.</li></ul><p>Good luck, and have fun!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=35b55a528afb" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>