<?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 Gilles Vandewiele on Medium]]></title>
        <description><![CDATA[Stories by Gilles Vandewiele on Medium]]></description>
        <link>https://medium.com/@gillesvandewiele?source=rss-3e8cbc53806e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*9uJwS_E_nZKfDjQjRMGndA.jpeg</url>
            <title>Stories by Gilles Vandewiele on Medium</title>
            <link>https://medium.com/@gillesvandewiele?source=rss-3e8cbc53806e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 17:20:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@gillesvandewiele/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[Winning the Kaggle Google Brain — Ventilator Pressure Prediction]]></title>
            <link>https://medium.com/data-science/winning-the-kaggle-google-brain-ventilator-pressure-prediction-2d4c90d831ec?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/2d4c90d831ec</guid>
            <category><![CDATA[hands-on-tutorials]]></category>
            <category><![CDATA[timeseries]]></category>
            <category><![CDATA[deep-dives]]></category>
            <category><![CDATA[pid-controller]]></category>
            <category><![CDATA[kaggle]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Fri, 12 Nov 2021 16:50:55 GMT</pubDate>
            <atom:updated>2021-11-15T22:15:06.235Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://towardsdatascience.com/tagged/hands-on-tutorials">Hands-on Tutorials</a></h4><h3>Winning the Kaggle Google Brain — Ventilator Pressure Prediction</h3><h4>On LSTMs, Transformers and PID controllers…</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/595/1*LdPma1aBeMRRe6I4Ldpbmg.png" /><figcaption>An artificial mechanical lung (<a href="https://commons.wikimedia.org/wiki/File:Q-vent.jpg">from Wikimedia</a>)</figcaption></figure><p>On the 4th of November, we managed to came out on top out of 2650 teams in the Google Brain — Ventilator Pressure Prediction, organized on Kaggle. In this blog post I would like to take you through the journey that bagged us the victory. A more summarized version of this write-up can be found on the <a href="https://www.kaggle.com/c/ventilator-pressure-prediction/discussion/285256">Kaggle forum</a> and we have published code for our <a href="https://www.kaggle.com/shujun717/1-solution-lstm-cnn-transformer-1-fold">LSTM + CNN Transformer model</a> and <a href="https://www.kaggle.com/group16/1-solution-pid-controller-matching-v1">PID matching</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/962/1*baWsDYHgZ9L1PNaQOF2XWw.png" /><figcaption>Winning eternal glory and $2500! Screenshot by Author</figcaption></figure><h3>An email from Kha…</h3><p>I was a little bit burnt down after finishing my PhD and after an unpleasant but short work experience. As a result, I was taking a bit of a hiatus from Kaggle in 2021, as you can see from my activity log. I participated a little bit in the “Rock, Paper, Scissors contest” and had a go at the “Indoor Location &amp; Navigation challenge”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/925/1*iUZcSQiVBuK4t43m4SksCQ.png" /><figcaption>Screenshot by Author</figcaption></figure><p>On the 23rd of September, <a href="https://www.kaggle.com/zidmie">Yves</a> and I received an email from <a href="https://www.kaggle.com/khahuras">Kha</a>. He spotted an interesting time series competition that was only lasting for 1 month on Kaggle. The competition appealed to me as I am quite familiar with time series data, and also a big fan of shorter competitions. Moreover, I know that when Kha, Yves and I team up, that good things often follow! I replied to Kha that I would be interested in joining, but had some things to take care of in real life first before I could really dive into it. <a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/DS_Ghent_Meetup_Liverpool_final.pdf">One of those things that had to be done was preparing &amp; giving a presentation on the third place solution Kha, Yves and I obtained in 2020 in the “Liverpool Ion Switching” competition.</a> Kha and Yves started working on the problem and making some good progress. Some time later, on the 6th of October, I joined them.</p><h3>Brief problem statement</h3><p>The goal of this competition is to predict the pressure within a mechanical lung on any given time step, based on how much the inspiratory solenoid valve is opened (u_in; a value between 0 and 100). We were given roughly 75000 training breaths and 50000 test breaths. Every breath consisted of an inspiratory phase and an expiratory phase, which was indicated by the provided u_out. Our submissions were only scored on inspiratory phase (so where u_out was equal to 0). Moreover, the breaths were recorded in a mechanical lung with different resistance and capacity properties, which were encoded in provided R and C variables.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*kOsI7cCrPw9E2vj9cukbtA.png" /><figcaption>An example of 1 training breath. We are provided with u_in, u_out, R &amp; C and are asked to predict the pressure. Image by Author</figcaption></figure><h3>Deep learning struggle</h3><p>From the public notebooks that were published in this competition, it was clear that LSTMs or any kind of temporal deep learning models would reign supreme. All three of us quickly adding features or making small modifications to these pipelines, but to no avail… It was clear that deep learning isn’t our forté. We then had a switch in mindset: <strong>“instead of trying to create one model, fitted on all train data, that is then used to make predictions for all test data, can’t we just focus on breaths individually instead and see whether we can model those to find patterns?”</strong></p><p>Yves, who has a background in physics, looked at PID controllers and quickly found a nice and simple post-processing trick that was able to give us a <strong>+0.004 boost on the LB</strong>, which is quite significant. Thanks to this post-processing trick, we were able to climb the leaderboard with a blend of slightly modified public notebooks, landing us a spot right out of the gold zone. The post-processing trick of Yves is rather simple to explain (but not that easy to find) and is based on the theory of PID controllers.</p><p>We could come up with a very simple formula: pressure = kt — (u_in/kp) . With kt and kp parameters of the algorithm that had to be tuned, u_in the input data and pressure the output data that we want to predict. <a href="https://arxiv.org/abs/2102.06779">The grid to search these parameters in was mentioned in a paper written by the organizers.</a> But this grid can easily be discovered without the paper by just applying linear regression to each breath in the training data (where we have u_in and pressure).</p><p>Now the question is, how do we know how good a certain set of parameters is for test breaths, as we do not have pressures to calculate an error. For this, we could make use of the discrete nature of the pressures. There are only 950 unique pressure values, with equal distances in between them. As such, if we fill in two candidate parameters kt and kp and the calculated pressure values align perfectly with these 950 unique pressure values, we have a match. This matching worked for roughly 2.5% of the data.</p><pre>KP_GRID = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, <br>           2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]<br>KT_GRID = [10, 15, 20, 25, 30, 35]</pre><pre>def match_breath(breath):<br>    u_in = breath[&#39;u_in&#39;].values<br>    inspiratory_len = np.sum(1 - breath[&#39;u_out&#39;])<br>    <br>    u_in = u_in[1:inspiratory_len]<br>    breath_mask = (u_in &gt; 0) &amp; (u_in &lt; 100)<br>    <br>    if np.sum(breath_mask) &lt; 2:<br>        return None, None, None, None<br>        <br>    for kt in KT_GRID:<br>        for kp in KP_GRID:<br>            preds = (kt - u_in / kp)<br>            preds_round = (preds-MIN_PRESSURE)/DIFF_PRESSURE<br>            tune_error = np.round(preds_round[breath_mask]) - preds_round[breath_mask]<br>            if np.sum(np.abs(tune_error)) &lt; 1e-6:<br>                return preds, kt, kp, breath_mask<br>            <br>    return None, None, None, None</pre><h3>Send in the reinforcements!</h3><p>After discovering the post-processing trick, we were not able to make any more significant improvements. We slowly saw our rank dropping on the LB, and it was clear that we would needed someone with more deep learning experience in order to obtain a good result in this competition. We messaged <a href="https://www.kaggle.com/shujun717">Shujun</a> who was just below the gold zone at that time. I knew that Shujun is extremely strong in deep learning as he got a solo gold medal with a unique and strong architecture in the <a href="https://www.kaggle.com/c/stanford-covid-vaccine">“OpenVaccine — Covid mRNA” competition</a> in which I participated too. Boy did he <strong>NOT</strong> disappoint.</p><p>Shujun’s deep learning architecture was a combination of LSTM cells, 1D convolutions, and transformers. LSTMs were necessary because of target pressure’s heavy dependence on previous time points. Convolutions in conjunction with transformers is a good combination to model global dependencies while making up for transformers’ inability to capture local interactions. The network was rather deep, and we ran into some gradient issues. Therefore, a new module called ResidualLSTM, which adds a Feedforward Network (FFN) and connects the input to the LSTM with the output after FFN with a residual connection, was created. The model works on the raw data in addition with a few lag and difference features, a cumulative sum of the u_in, and one-hot-encoded R &amp; C features.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*RJgpR5iffYzmZBLY.png" /><figcaption>The LSTM + CNN Transformer architecture. Image by Co-Author Shujun.</figcaption></figure><p>We ensembled our current blend with Shujun’s blend of different runs of his model and applied our PP trick. <strong>Boom</strong>, we were in the gold!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/1*mjDnTgYTlCAZ6_-ovaqJ3g.png" /><figcaption>Image by Author</figcaption></figure><p>We tried suggesting some ideas to Shujun to implement in his pipeline, and also tried adding some features so the pipeline (as his pipeline was leveraging features). But again, we were not successful.</p><p>A few days later, we felt that we needed another unique deep learning pipeline for our blend. This is where <a href="https://www.kaggle.com/callmeb">Riccardo enters the story</a>! At the time when we messaged him, Riccardo was only a few spots below us. He had an LSTM architecture up and running that converged on just the raw data. No feature engineering, no fancy stuff, just raw data and a lot of epochs. The trick was to have a good learning rate scheduler. We opted for a ReduceLROnPlateau with a patience of 30 epochs. This was in contrast with the fast annealing schedulers typically used within the public notebooks, which were susceptible to overfitting. This can be seen when we compare our validation loss curves to those of the public notebooks, as displayed below. Here the red (stakes) curve corresponds to the public notebooks and quickly overfits.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-Lk77QWkqTICbOZ9KyYsWg.png" /><figcaption>Image by Author</figcaption></figure><p>This approach even scored better than the LSTM + 1D CNN Transformer Encoder. The blend of these pipelines gave us the fourth spot on the leaderboard. <strong>We decided to change our ambitions from a gold medal to winning money.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*RMryr7Z9aMV_xVxiMcE8nA.png" /><figcaption>Image by Author</figcaption></figure><p>Again, all of us focused on improving the two pipelines we had up and running. Making slight modifications to both pipelines or adding features to the transformer pipeline. Only extremely marginal improvements were made, and the gap with the competitors ahead of us was too big. <strong>Surely, there was something hidden in the data that they had found and we did not yet…</strong></p><h3>The best birthday gift ever</h3><p>On the 26th of October, my birthday, I decided to learn some more about PID (<strong>P</strong>roportional - <strong>I</strong>ntegral - <strong>D</strong>erivative) controllers, as those were a core concept in the organizers their paper as well. Moreover, our post-processing trick came from Yves looking into these PID controllers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/257/1*MYtVcyWcdRcMs7zzTMduGw.png" /><figcaption>Let’s poke this rabbit hole… Image by Author</figcaption></figure><p>I played around with the <a href="https://github.com/m-lundberg/simple-pid">simple-pid</a> package in Python as this package already implements the PID formulas. I was able to reproduce our post-processing trick with this package as well. However, for most breaths I was not able to find a match. That was until I decided to play around with the code and the integral term specifically. There are multiple ways to calculate the Integral term of PID controllers, and the package only included the vanilla implementation. I decided to plug in some other alternatives and suddenly, I had a breakthrough… <strong>WHAT A BIRTHDAY GIFT! </strong>The following code snippet (based on the simple-pid package) was able to model pressure-&gt;u_in perfectly for some breaths:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/864/1*xlvDMpYanM7EpBG-jl7DrQ.png" /><figcaption>Close, but not yet… Still a huge breakthrough! Image by Author</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_7kWHJxBhsB2iy0Akexg7A.png" /><figcaption>A few hours later after fixing some details… Image by Author</figcaption></figure><p>Here is the code snippet that was able to perfectly model pressure to u_in for some of the breaths:</p><pre>def generate_u_in(pressure, time_step, kp, ki, kt, integral=0):<br>    dt = np.diff(time_step, prepend=[0])<br>    preds = []<br>    for j in range(32):<br>        error = kt - pressure[j]<br>        integral += (error - integral) * (dt[j] / (dt[j] + 0.5))<br>        preds.append(kp * error + ki * integral)<br>    return preds</pre><p>I thought we had a new nice post-processing trick on our hands, and sent this information to Yves. Yves made something much much bigger out of it. He came up with some code that was able to match the pressures perfectly.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OO_Iqh9S4GvgX5KYApgGSg.png" /><figcaption>Can you feel the excitement? Image by Author</figcaption></figure><h3>The perfect match</h3><p>We can write the “vanilla” equation of a PID controller (that corresponds to the generate_u_in snippet I provided):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Dx6KYbo0W1ydQsoG.png" /></figure><p>With epsilon equal to target — pressure where target represents the ideal pressure that is set by the user. Now gamma, which is the weight of the derivative term, was always set to zero by the organizers. So we only had to focus on the first (proportional) and second (integral) term. Our previously discussed post-processing technique actually corresponds to this equation with beta set to 0. Let’s rewrite the second integral term for ease of notation. Moreover, the integral term was implemented by a weight decay as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_emMEbtmkIGJs9bq.png" /></figure><p>With delta_t the difference in time between timestep t and t-1 and tau a constant, which was equal to 0.5 for this data. We can isolate the integral term from the PID equation, in order to calculate it for any point in time. This avoids having to propagate this across the entire signal:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*OoBG2tv_aCN_su9J.png" /></figure><p>With these equations, we are all set for our matching algorithm. Our matching algorithm to fill in the pressure for a given breath at timestep t, for a given configuration of parameters (target, alpha and beta or referred to as <strong>kt, kp and ki</strong> respectively in the remainder of this post) goes as follows:</p><ol><li>Take two random pressure values P0 and P1 . There are 950 possible pressure values and thus 950*950 possible combinations.</li><li>Calculate I0 = (u_in[t - 1] - kp * (kt - P0))/ki</li><li>Calculate I1 = I0 + (kt - P1 - I0) * (dt / (dt + 0.5))</li><li>If kp * (kt - P1) + ki * I1 == u_in[t] we have a match and we can fill in P1 for pressure[t]</li></ol><p>In code:</p><pre>P_RANGE = np.arange(<br>  MIN_PRESSURE, <br>  MAX_PRESSURE + DIFF_PRESSURE, <br>  DIFF_PRESSURE<br>)<br>for P0 in P_RANGE:<br>    for P1 in P_RANGE:<br>        I0 = (u_in[t - 1] - kp * (kt - P0))/ki<br>        I1 = I0 + (kt - P1 - I0) * (dt / (dt + 0.5))<br>        u_in_hat = kp * (kt - P1) + ki * I1<br>        if abs(u_in_hat - u_in[t]) &lt; 1e-8:<br>            print(P0, P1, pressure[t-1:t+1])</pre><p>However, this code is <strong>rather slow</strong>. This is because 950*950 combinations need to be tried for every possible parameter combination. kp and ki have 20 possible values and kt has 6 possible values, in total we thus have 950*950*20*20*6 possible combinations. However, for a fixed P0 we notice that abs(u_in_hat — u_in[t]) grows linearly across the for-loop. As such, we can extrapolate this with just 2 measurements. If the intersection of this extrapolated function with the x-axis occurs at an integer (or close to an integer), our if-condition would have evaluated to True in an iteration of our inner for-loop.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/935/0*-V1U4NZFkOimZ--6.png" /><figcaption>Image by Author</figcaption></figure><p>This observation allows us to speed up the code with a factor of 950.</p><pre>for P0 in P_RANGE:<br>    I0 = (u_in[t - 1] - kp * (kt - P0))/ki<br>    <br>    # Calculate 2 points for P1 so we can get the slope<br>    I11 = I0 + (kt - MIN_PRESSURE - I0) * (dt / (dt + 0.5))<br>    u_in_hat1 = kp * (kt - MIN_PRESSURE) + ki * I11<br>    <br>    I12 = I0 + (kt - MIN_PRESSURE2 - I0) * (dt / (dt + 0.5))<br>    u_in_hat2 = kp * (kt - MIN_PRESSURE2) + ki * I12<br>    <br>    slope = u_in_hat2 - u_in_hat1<br>    x_intersect = (u_in[t] - u_in_hat2) / slope<br>    if abs(np.round(x_intersect) - x_intersect) &lt; 1e-8:<br>        print(P0, MIN_PRESSURE + (x_intersect + 1) * DIFF_PRESSURE)</pre><h3>Turn it up! Bring the noise!</h3><p>With the code above, we were able to match a lot of pressures. But many of them still remained unmatched. In the paper of the organizers, it was explained that artificial noise was added to the u_in data. We set out on an endeavour to remove this noise. Let us first look at the output of the current version of a matching algorithm on a particular breath (train breath id 17)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/0*rWXXkz3yMlwqQgen.png" /><figcaption>Image by Author</figcaption></figure><p>As one notices, the first value of the u_in and some values in the middle were not fully matched. The first values of all breaths are noisy and are not matchable, but the points in the middle should be matchable… Let us start from index 5 and call our generate_u_in code on the provided pressures to generate “ideal u_in values” and subtract this from the u_in we are provided.</p><pre>kp, ki, kt = 1., 3., 30<br>I5 = (u_in[4] - kp * (kt - pressure[4]))/ki<br>u_in_hat = generate_u_in(pressure[5:], timestep[4:], kp, ki, kt, integral=I5)<br>noise = u_in[5:32] - u_in_hat[:-5]<br>plt.plot(timestep[5:32], noise, &#39;-o&#39;)<br>plt.title(&#39;noise&#39;)<br>plt.show()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/377/0*lIpncrwMIBCM0fWr.png" /><figcaption>Image by Author</figcaption></figure><p>The difference between the ideal u_in values and the provided u_in values form a nice triangle, except on the turning point / peak of the triangle. The key insight is that the slope of this noise ((np.diff(noise) / np.diff(timestep[5:32]))) will be equal for consecutive points on this triangle. We can also rewrite our integral calculation to work backwards.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6UlkIcbZ5zhp89iA.png" /></figure><p>Strapped with these two insights, we were able to match a lot more data:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/0*eeMa_Ux9vFiXcIVk.png" /><figcaption>Image by Author</figcaption></figure><h3>Putting it together</h3><p>Given our DL models and matching algorithm, our approach was rather simple:</p><ol><li>Generate predictions with our two DL models. Train them in 10-fold cross validation at multiple seeds. This gives us multiple models with slight variations. Take the (weighted) median of these models as an ensembling technique as that is typically better than a mean when MAE is the metric.</li><li>From these predictions, apply our matching algorithm. If we find a match, replace the prediction of the DL algorithm by the matcher. If there is not a match, keep the DL prediction.</li></ol><p>In total we were able to roughly match 66% of the data, which gave us a <strong>HUGE </strong>boost on the leaderboard.</p><h3>Closing time</h3><p>This was my first victory on Kaggle. While I admit that the PID controller matching was a bit cheeky, I am still extremely proud of our result as only 2 teams out of 2650 were able to find this exploit. Moreover, we were the only team that was able to match the noise within the u_in data as well. I would like to thank my team mates <a href="https://www.kaggle.com/zidmie">zidmie</a>, <a href="https://www.kaggle.com/khahuras">kha</a>, <a href="https://www.kaggle.com/shujun717">shujun</a> and <a href="https://www.kaggle.com/callmeb">B</a> as without them this result would not have been possible!</p><p>In case you have any questions or something is unclear, feel free to leave some comments or contact me through some other medium (pun intended).</p><h3>References</h3><ol><li><a href="https://arxiv.org/abs/2102.06779">Organizers Paper</a></li><li><a href="https://www.kaggle.com/c/ventilator-pressure-prediction/discussion/285256">Kaggle Forum write-up</a></li><li><a href="https://www.kaggle.com/group16/1-solution-pid-controller-matching-v1">PID Matching Code + Explanation</a> (Kaggle)</li><li><a href="https://github.com/GillesVandewiele/google-brain-ventilator">PID Matching Code + Explanation (Github)</a></li><li><a href="https://www.kaggle.com/shujun717/1-solution-lstm-cnn-transformer-1-fold">LSTM + CNN Transformer code (Kaggle)</a></li><li><a href="https://github.com/Shujun-He/Google-Brain-Ventilator">LSTM + CNN Transformer code (Github)</a></li><li><a href="https://github.com/whoknowsB/google-brain-ventilator-pressure-prediction">LSTM on raw data code (Github)</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2d4c90d831ec" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/winning-the-kaggle-google-brain-ventilator-pressure-prediction-2d4c90d831ec">Winning the Kaggle Google Brain — Ventilator Pressure Prediction</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to Create Representations of Entities in a Knowledge Graph using pyRDF2Vec]]></title>
            <link>https://medium.com/data-science/how-to-create-representations-of-entities-in-a-knowledge-graph-using-pyrdf2vec-82e44dad1a0?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/82e44dad1a0</guid>
            <category><![CDATA[hands-on-tutorials]]></category>
            <category><![CDATA[representation-learning]]></category>
            <category><![CDATA[embedding]]></category>
            <category><![CDATA[unsupervised-learning]]></category>
            <category><![CDATA[knowledge-graph]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Mon, 02 Nov 2020 12:47:30 GMT</pubDate>
            <atom:updated>2020-11-02T21:51:30.407Z</atom:updated>
            <content:encoded><![CDATA[<h4><a href="https://towardsdatascience.com/tagged/hands-on-tutorials">Hands-on Tutorials</a></h4><h4>A tutorial on how to tackle downstream ML tasks on data represented in a Knowledge Graph.</h4><h3>Table of contents</h3><ul><li><a href="#1f07">Representing data with Knowledge Graphs</a></li><li><a href="#294a">Running example: countries in DBpedia</a></li><li><a href="#0861">Creating entity embeddings with RDF2Vec</a></li><li><a href="#08bc">Introducing pyRDF2Vec</a></li><li><a href="#6a7a">Biased walking or sampling strategies</a></li><li><a href="#20d7">Walk modifications and transformations</a></li><li><a href="#240f">Loading KGs with pyRDF2Vec</a></li><li><a href="#a134">Creating our first embeddings</a></li><li><a href="#4037">Tuning the hyper-parameters</a></li><li><a href="#def9">Trying different walking strategies</a></li><li><a href="#62a0">Sampling Deeper Walks</a></li><li><a href="#1c6e">Shortcomings of RDF2Vec and research challenges</a></li><li><a href="#8a76">Code and data availability</a></li></ul><h3>Representing Data With Knowledge Graphs</h3><p><strong>Graphs</strong> are data structures that are useful to represent ubiquitous phenomena, such as social networks, chemical molecules and recommendation systems. One of their strengths lies in the fact that they explicitly model relations (i.e. <strong>edges</strong>) between individual units (i.e. <strong>nodes</strong>), which adds an extra dimension to the data.</p><p>We can illustrate the added value of this data enrichment using the <a href="https://relational.fit.cvut.cz/dataset/CORA">Cora citation network</a>. This dataset contains a bag-of-words representation for a few hundred papers and the citation relations between each of these papers. If we apply dimensionality reduction (t-SNE) to create a 2D plot of the bag-of-words representations (Figure 1, left), we can see clusters (they are colored according to their research topic) arise but they overlap. If we produce an embedding with a graph network (Figure 1, right), that takes into account the citation information, we can see the clusters being better separated.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/493/0*y332aTSAuQIkzz_K.png" /><figcaption><strong>Figure 1:</strong> left: A t-SNE embedding of the bag-of-words representations of each paper. right: An embedding produced by a graph network that takes into account the citations between papers. source: <a href="https://arxiv.org/abs/1809.10341">“Deep Graph Infomax” by Velickovic et al.</a></figcaption></figure><p><strong>Knowledge Graphs </strong>(KG) are a specific type of graph. They are <em>multi-relational</em> (i.e. there are different edges for different types of relations) and <em>directed</em> (i.e. the relations have a subject and object). These properties allow to represent information from heterogeneous sources in a uniform format. We can convert the Knowledge Graphs to regular directed graphs, which facilitates further analysis, as shown in Figure 2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1017/0*JpUPmG3LU1pcCR-b.png" /><figcaption><strong>Figure 2:</strong> Converting a multi-relational directed KG in a regular directed graph. Image by author.</figcaption></figure><h3>Running Example: Countries in DBpedia</h3><p>We will use a running example throughout this post. Let’s start by focusing on creating representations for a few randomly chosen countries from all over the world. We will extract information for each of the countries from <a href="https://wiki.dbpedia.org/about">DBpedia</a>, a large general-purpose KG that is created from <a href="http://www.wikipedia.org/">Wikipedia</a>.</p><p>Let’s take a look at how the KG looks in the neighbourhood of a specific country: 🇧🇪 Belgium 🇧🇪. This process is analogous to going to its <a href="http://dbpedia.org/page/Belgium">corresponding DBpedia page</a> and then recursively clicking on all the links on that page. We depict this below in Figure 3. We notice that expanding this neighbourhood iteratively makes things complex quickly, even though we introduced some simplifications by removing some of the parts. Nevertheless, we see that DBpedia contains some useful information about Belgium (e.g., its national anthem, largest city, currency, …).</p><p>We created a custom dataset with country information by using the <a href="https://dbpedia.org/sparql">DBpedia SPARQL endpoint</a>. We retrieved a list of countries from the <a href="https://www.uni-mannheim.de/dws/research/resources/sw4ml-benchmark/">University of Mannheim “Semantic Web for Machine Learning” repository</a>. Each of the countries contains information regarding their inflation and academic output. This information is binarized into “high” and “low” (so two binary classification tasks). Moreover, for each of the countries we retrieved their continent (Europe, Asia, Americas, Africa or Oceania), which gives us a 5-class classification task. The KG with the information about these countries is a subset from DBpedia: for each country, we retrieved all information by expanding the KG three times. This process corresponds exactly to what is depicted in Figure 3. Due to a rate limitation placed on the SPARQL endpoint, only a maximum of 10000 nodes at depth 3 and their parents are included. The KG (in Turtle syntax) can be downloaded <a href="https://www.dropbox.com/s/naysvkn55jqxxeo/countries.ttl">here</a>, the CSV files with the list of countries and their labels can be downloaded <a href="https://www.dropbox.com/s/ymo3pjfqzscsvey/countries.csv">here</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-fo07n-06Obzqks4hoGQyg.png" /><figcaption><strong>Figure 3:</strong> Recursively expanding the knowledge graph makes things complex quickly. Image by author.</figcaption></figure><h3>Creating Entity Embeddings With RDF2Vec</h3><p><strong>RDF2vec</strong> stands for Resource Description Framework To Vector. It is an unsupervised, task-agnostic algorithm to numerically represent nodes in a KG, allowing them to be used for further (downstream) machine learning tasks. RDF2Vec builds on top of existing natural language processing techniques: it combines insights from <a href="https://dl.acm.org/doi/pdf/10.1145/2623330.2623732">DeepWalk</a> and <a href="https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf">Word2Vec</a>. Word2Vec is able to generate embeddings for each word in a provided collection of sentences (often called a corpus). To generate a corpus for a KG, we extract walks. Extracting walks is similar to visiting a DBpedia page of an entity and clicking on links. The number of clicks you make is equivalent to the number of hops in a walk. An example of such a walk, again for Belgium, would be: <a href="http://dbpedia.org/resource/Belgium">Belgium</a> -&gt; <a href="http://dbpedia.org/ontology/capital">dbo:capital</a> -&gt; <a href="http://dbpedia.org/resource/City_of_Brussels">City of Brussels</a> -&gt; <a href="http://dbpedia.org/ontology/mayor">dbo:mayor</a> -&gt;<a href="http://dbpedia.org/resource/Yvan_Mayeur">Yvan Mayeur</a>. Note that we make no distinction between predicates/properties (e.g., dbo:capital and dbo:mayor) and entities (e.g., Belgium, Brussels, Yvan Mayeur, …) in our walks, as explained in Figure 2. Each walk can now be seen as a sentence, and the hops in that walk correspond to the tokens (words) of a sentence. Once we extracted a large number of walks rooted at the entities we want to create embeddings for, we can provide that as a corpus to Word2Vec. Word2Vec will then learn embeddings for each unique hop which can then be used for ML tasks.</p><h3>Introducing pyRDF2Vec</h3><p>pyRDF2Vec is a repository that contains a Python implementation of the <a href="http://rdf2vec.org/">RDF2Vec</a> algorithm. On top of the original algorithm, different extensions are implemented as well.</p><blockquote><strong><em>In this tutorial, I will explain how we can generate embeddings of entities in KG using pyRDF2Vec. Moreover, I will briefly explain some of the extensions to RDF2Vec and how those can be used within pyRDF2Vec.</em></strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*dgij9Wdt9LgEo-CCltet8g.png" /><figcaption>Image taken from <a href="https://github.com/IBCNServices/pyRDF2Vec">our repository</a>.</figcaption></figure><h3>Biased Walking or Sampling Strategies</h3><p>Now, as can be noticed from Figure 3, the number of possible that walks that we can extract grows exponentially in function of the depth. This becomes problematic when we are using large KGs, such as DBpedia. In the <a href="https://madoc.bib.uni-mannheim.de/41307/1/Ristoski_RDF2Vec.pdf">original RDF2Vec paper</a>, walks were just randomly sampled from the graph but <a href="https://dl.acm.org/doi/pdf/10.1145/3102254.3102279">Cochez et al. proposed several metrics to bias the walks</a>. These walks were then called biased walks, but we will refer to them as sampling strategies in line with the pyRDF2Vec terminology. An example of a possible sampling strategy is shown in Figure 4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/791/1*Tap3__Gh5xtia5A6FA2NzA.png" /><figcaption><strong>Figure 4:</strong> One possible way to sample the next hop in a walk, would be to scale the weights in function of the number of outgoing edges. This is only one example, there are many different metrics (based on frequency, PageRank, degrees, …). Image by author.</figcaption></figure><h3>Walk Modifications and Transformations</h3><p>Up until now, we explained the walking algorithm as continuously sampling from the neighbours of a node until a certain depth is reached. However, we can make modifications to this algorithm (extraction algorithms) or we can apply post-processing on the walks to incorporate extra information (transformation algorithms). <a href="https://arxiv.org/pdf/2009.04404.pdf">This is what we have been researching at IDLab</a>. These strategies, applied on a simple example, can be seen in Figure 5.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*MZboCTMObVfEu_GW7J6WiQ.png" /><figcaption><strong>Figure 5:</strong> Different strategies to extract walks (depth 2) from a graph. In this figure, A and F are the roots from which we want to extract walks. C and H belong to the same community (community detection). source: <a href="https://arxiv.org/pdf/2009.04404.pdf">“Walk Extraction Strategies for Node Embeddings with RDF2Vec in Knowledge Graphs” by Vandewiele et al. </a>(blog author).</figcaption></figure><p>Now that we have introduced these modified walking strategies, we now discussed each of the three main building blocks of the RDF2Vec algorithm: (i) a <strong>walking strategy</strong>, (ii) a <strong>sampling strategy</strong>, and (iii) an <strong>embedding algorithm</strong> (NLP). As we will further discuss, each of these building blocks are configurable in pyRDF2Vec.</p><h3>Loading KGs With pyRDF2Vec</h3><p>KGs are often represented in Resource Description Framework (RDF) format. pyRDF2Vec can easily load files in different RDF syntaxes by wrapping around <a href="https://rdflib.readthedocs.io/en/stable/">rdflib</a>. This will load the entire KG into RAM memory. However, this becomes problematic when the KG is larger than the available RAM memory. We therefore also support interaction with endpoints: the KG can be hosted on some server and our KG object will interact with that endpoint whenever necessary. This drastically reduces the required RAM memory at a cost of higher latencies.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6e4ed1e5e72a0b816aee78a69fdaefa0/href">https://medium.com/media/6e4ed1e5e72a0b816aee78a69fdaefa0/href</a></iframe><h3>Creating Our First Embeddings</h3><p>Now that we have our KG loaded in memory, we can start creating embeddings! In order to do this, we create an RDF2VecTransformer and then call the fit() function with the freshly loaded KG and a list of entities. Once the model is fitted, we can retrieve their embeddings through the transform() function. One thing that is different from the regular scikit-learn flow (where we call fit() on the train data and predict() or transform() on the test data) is that both the train and test entities have to be provided to the fit() function (similar to how t-SNE works in scikit-learn). Since RDF2Vec works unsupervised, this does not introduce label leakage.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/92805725d500fe9a343b25a41d914df4/href">https://medium.com/media/92805725d500fe9a343b25a41d914df4/href</a></iframe><p>The code snippet above will give us a list of lists. For each of the provided entities to the transform method, a 100-dimensional embedding will be returned. Now in order to inspect these embeddings with the human eye, we need to further reduce the dimensionality. One great technique to do this, is by using <a href="https://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html">t-SNE</a>. We can do this using the following code snippet:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06513f95881e816d3e3722954b11fb45/href">https://medium.com/media/06513f95881e816d3e3722954b11fb45/href</a></iframe><p>Which gives us the result shown in Figure 6.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/1*gzX8W7M0q7wHSPQuw3EV1w.png" /><figcaption><strong>Figure 6:</strong> a t-SNE plot of our initial embeddings. We can start to see clusters of countries arise. Image by Author.</figcaption></figure><p>Now let’s take a look at how good these embeddings are in order to solve the three ML tasks we have discussed: two binary classification tasks (high/low inflation and high/low academic output) and a multi-class classification task (predict the continent). It should be noted that, since RDF2Vec is unsupervised, during the creation of these embeddings, this label information was never used! RDF2Vec is task-agnostic, the projection from our nodes to an embedding is not tailored towards a specific task, and the embeddings can be used for multiple different downstream tasks. Let’s create an utility function that takes as input the produced embeddings and then performs classification for all three tasks:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6c0fe650a33cd28c9e84b74391e1ef8a/href">https://medium.com/media/6c0fe650a33cd28c9e84b74391e1ef8a/href</a></iframe><p>Now let’s call classify(walk_embeddings) to take a look at the performance of our baseline embeddings:</p><pre><strong>Research Rating</strong><br>Accuracy = 0.765625<br>[[26  8]<br> [ 7 23]]<br><br><strong>Inflation Rating</strong><br>Accuracy = 0.5882352941176471<br>[[14 16]<br> [12 26]]<br><br><strong>Continent</strong><br>Accuracy = 0.6716417910447762<br>[[13  3  1  1  0]<br> [ 4 11  0  1  0]<br> [ 0  1  7  3  0]<br> [ 1  3  1 14  0]<br> [ 0  1  0  2  0]]</pre><p>The accuracies for the research rating, inflation and continent classification are respectively equal to 76.56%, 58.82% and 67.16%. While these accuracies are far from perfect, it does show that some information for all these tasks is present within the generated embeddings. One possible reason for these lower accuracies is that only a subset of data from DBpedia was used due to rate limitations of its public API. Moreover, we only used default hyper-parameters to generate our embeddings.</p><h3>Tuning the Hyper-Parameters</h3><p>As mentioned before, each of the three building blocks of the RDF2Vec algorithm (walking algorithm, sampling strategy and embedding technique) are configurable. For now, let’s try to extract deeper walks and generate larger embeddings:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/af838503cd42c675728ac6704572e661/href">https://medium.com/media/af838503cd42c675728ac6704572e661/href</a></iframe><p>We specify that we want to use the <em>random</em> walking strategy to extract walks with a depth of 3, this corresponds to following 3 links from a certain DBpedia page, or taking 6 hops in our converted KG (see Figure 1). We also specify that we want to extract <strong>all</strong> possible walks of depth 3 exhaustively for each entity, indicated by the None argument. We do not specify any sampling strategy but do specify that we want to use the Word2Vec embedding technique to produce embeddings of size 500. This hyper-parameter configuration gives us the following accuracies:</p><pre><strong>Research Rating</strong><br>Accuracy = 0.78125<br>[[25  9]<br> [ 5 25]]<br><br><strong>Inflation Rating</strong><br>Accuracy = 0.6470588235294118<br>[[14 16]<br> [ 8 30]]<br><br><strong>Continent</strong><br>Accuracy = 0.6865671641791045<br>[[15  0  0  3  0]<br> [ 6  9  0  1  0]<br> [ 1  2  6  2  0]<br> [ 0  3  0 16  0]<br> [ 0  0  0  3  0]]</pre><p>As we can see, the accuracy has improved for two of the three tasks while remaining the same for the third task (inflation classification).</p><h3>Trying Different Walking Strategies</h3><p>pyRDF2Vec allows us to use different walking strategies, an overview of the different strategies is provided in Figure 5. Moreover, we can combine different strategies: pyRDF2Vec will extract walks with each strategy and concatenate the extracted walks together before providing it to the embedding technique. Let’s try combining several walking strategies:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f79a510a5543dcd8156d29f8169ff500/href">https://medium.com/media/f79a510a5543dcd8156d29f8169ff500/href</a></iframe><p>The accuracies we now get are:</p><pre><strong>Research Rating</strong><br>Accuracy = 0.71875<br>[[24 10]<br> [ 8 22]]<br><strong><br>Inflation Rating</strong><br>Accuracy = 0.6764705882352942<br>[[14 16]<br> [ 6 32]]<br><br><strong>Continent</strong><br>Accuracy = 0.7910447761194029<br>[[15  0  0  3  0]<br> [ 5 11  0  0  0]<br> [ 2  0  9  0  0]<br> [ 0  1  0 18  0]<br> [ 0  1  0  2  0]]</pre><p>So an improvement for the Inflation Rating and Continent task but a decrease in performance for the Research Rating.</p><h3>Sampling Deeper Walks</h3><p>Now if we want to extract deeper walks, we quickly run into memory issues, since the number of walks grow exponentially in function of the walk depth. This is where sampling strategies come into play. As a final experiment, let’s sample 5000 walks of depth 6 using the walking strategies from the previous section:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/73e5965960c7d17c0e5254d273f17d84/href">https://medium.com/media/73e5965960c7d17c0e5254d273f17d84/href</a></iframe><p>In total, 854901 walks were extracted. This gives us the following accuracies:</p><pre><strong>Research Rating</strong><br>Accuracy = 0.671875<br>[[30  4]<br> [17 13]]<br><br><strong>Inflation Rating</strong><br>Accuracy = 0.5<br>[[14 16]<br> [18 20]]<br><br><strong>Continent</strong><br>Accuracy = 0.8059701492537313<br>[[17  0  0  1  0]<br> [ 4 10  0  2  0]<br> [ 0  2  9  0  0]<br> [ 0  1  0 18  0]<br> [ 0  3  0  0  0]]</pre><p>So only an improvement for the continent classification and a significant deterioration for the two other tasks. Of course, one could tune the many hyper-parameters of the RDF2VecTransformer (the walking &amp; sampling strategy and their corresponding hyper-parameters) and the Random Forest (or any other classification technique) to obtain optimal accuracies, but we leave that as an exercise to the reader!</p><h3>Shortcomings of RDF2Vec and Research Challenges</h3><p>There are a few shortcomings in the current version of RDF2Vec that can be identified that require further research to tackle them:<br>– <strong>The original RDF2Vec implementation does not incorporate the most recent insights from the NLP domain:</strong> since the inception of RDF2Vec, on 2017, many advancements in the domain of NLP have been made. We are currently working on implementing different NLP embedding techniques (such as BERT) into pyRDF2Vec.<br><strong>– The expressiveness of embeddings produced by random walks can be limited:</strong> walks are only single chains, the information they capture is somewhat limited. The walking strategies try to alleviate this shortcoming, but further research in this direction is needed. Moreover, we could probably combine walks generated by different strategies together.<br><strong>– RDF2Vec does not scale to large KGs:</strong> as the number of possible walks that can be extracted grows exponentially with depth, RDF2Vec does not scale well to KGs with a large number of nodes, especially when it contains many highly-connected nodes. The sampling strategies improve scalability, but more research can be done.<br><strong>– RDF2Vec cannot deal well with numerical values in the KG:</strong> currently, all hops in the walks, which correspond to nodes from the KG, are handled as categorical data. This is sub-optimal for ordinal data (e.g., the number of inhabitants and the size of a country).<br>– <strong>RDF2Vec cannot deal with volatile data: </strong>as mentioned, both the train and test data need to be provided to our fit() method. But what if some of our test data is not yet available? There are techniques that can help here, such as online and incremental learning.</p><p>We hope, by releasing pyRDF2Vec, to provide a toolkit that can facilitate research to tackle these challenges.</p><h3>Code and Data Availability</h3><p><a href="http://github.com/IBCNServices/pyRDF2Vec">The pyRDF2Vec repository can be found on Github</a>. Feel free to give us a star if you like the repository, it is greatly appreciated! Moreover, we welcome all kinds of contributions.</p><p>The custom dataset used throughout this blog post can be downloaded: <a href="https://www.dropbox.com/s/naysvkn55jqxxeo/countries.ttl">KG</a> and <a href="https://www.dropbox.com/s/ymo3pjfqzscsvey/countries.csv">CSV</a>. We also provide all the code in a <a href="https://colab.research.google.com/drive/1kTj7_tEgI2cUWzaUkXfGtwJ-QMjW3c2-?usp=sharing">Google Colab notebook</a> so you can run it yourself interactively from your browser!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=82e44dad1a0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/how-to-create-representations-of-entities-in-a-knowledge-graph-using-pyrdf2vec-82e44dad1a0">How to Create Representations of Entities in a Knowledge Graph using pyRDF2Vec</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Predicting mRNA Degradation using GNNs and RNNs in the Search for a COVID-19 Vaccine]]></title>
            <link>https://medium.com/data-science/predicting-mrna-degradation-using-gnns-and-rnns-in-the-search-for-a-covid-19-vaccine-b3070d20b2e5?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/b3070d20b2e5</guid>
            <category><![CDATA[covid19]]></category>
            <category><![CDATA[rna]]></category>
            <category><![CDATA[graph-neural-networks]]></category>
            <category><![CDATA[kaggle]]></category>
            <category><![CDATA[recurrent-neural-network]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Fri, 16 Oct 2020 13:26:10 GMT</pubDate>
            <atom:updated>2020-10-22T06:47:18.945Z</atom:updated>
            <content:encoded><![CDATA[<h4>A write-up of the fourth place solution to the Kaggle OpenVaccine competition</h4><p>The current COVID-19 pandemic requires an effective vaccine in order to win the fight against this virus. Researchers from Stanford University are studying mRNA vaccines as these could quickly provide a candidate solution. One challenge to these types of vaccines is their stability: they tend to spontaneously degrade unless kept under intense refrigeration. In order to find a stable mRNA sequence, the people from Stanford University reached out to the Kaggle community in the <a href="https://www.kaggle.com/c/stanford-covid-vaccine/overview">OpenVaccine: COVID-19 mRNA Vaccine Degradation Prediction</a> competition. The competition launched on 11 September and lasted for only 26 days, which is unusually short for Kaggle due to its urgency. There was a prize-pool of $25,000 for the top three competitors. <a href="https://www.kaggle.com/bsteenwi"><strong>Bram Steenwinckel</strong></a><strong>, </strong><a href="https://www.kaggle.com/mtinti"><strong>Michele Tinti</strong></a><strong> and I were able to achieve the fourth position, missing out on the money by an inch! </strong>In the hope that we could even have the slightest contribution in the search for a COVID-19 vaccine, we are publishing this blog post that discusses our solution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/952/1*7l2tKZsEyKNxCAZSDAY_eQ.png" /><figcaption>Our team “FromTheWheel &amp; Dyed &amp; StoneShop” got fourth place! Our team name consists of our family names translated (quite literally) from our native languages (Dutch and Italian) to English. <a href="https://www.kaggle.com/c/stanford-covid-vaccine/leaderboard">This image is a screenshot of the Kaggle Leaderboard.</a></figcaption></figure><h4>Problem statement</h4><p>The goal of this competition was to predict, for each of the bases (A, C, G or U) in the provided RNA sequences, the reactivity and degradation under certain circumstances such as incubation with or without magnesium in high temperatures or high pH. In summary, we have to predict three continuous values (i.e. regression) for each of the bases in the sequence (i.e. sequence-to-sequence).</p><p>The training set consists of 2400 sequences of length 107, the public test set contains 629 sequences of length 107 and the private test set consists of 3005 sequences of length 130. There is thus a difference in the sequence length in the private test data. It is therefore of great importance that the model has built-in invariance to the sequence length. Moreover, the sequences are only partially scored. For the train and public test set, only the first 68 of 107 bases are scored while for the private test set, the first 91 out of 130 bases are scored. An example of the targets for one of the training sequences is provided below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/778/1*gXZrewB4XUXlb4FGXAEmDQ.png" /><figcaption>The time series of target values for one of the training sequences. Image by Author.</figcaption></figure><p>We can also display these target values on the RNA sequence graph directly as done for the reactivity in the example below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fPpAvO1sU8ztiJE3qkbxEg.png" /><figcaption>One of the possible foldings of a RNA sequence. The node colors depict the reactivity values (red = high, blue = low). Notice that 107–68 nodes are not colored as no targets are specified for the tail of the sequence. Image by Author.</figcaption></figure><h4>High-level solution overview</h4><p>By looking at the targets, it is clear that a certain value is correlated with its neighbouring values in the time series. Recurrent Neural Networks are a perfect fit for these kinds of situations, as their built-in memory takes into account the nearby predicted values. We learn a representation for each of the bases in our sequence and pass these through 2 (bi-directional) RNN layers. The representation for each node is learned by using both information of the node itself and relationship or edge information. As can be seen in the introduction, the RNA sequence can be represented by a graph, and relations between certain bases in the sequence are present. We use Graph Layers to aggregate this relationship information. Our final solution consists of a blend of 4 different models, in which we vary the RNN layers (LSTM+LSTM, LSTM+GRU, GRU+LSTM and GRU+GRU). Some details are left out from this high-level overview. One important detail is that we pre-trained the network until the RNN layers as an Auto-Encoder. This allowed us to train on the unlabeled test data as well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/812/1*BJ3-OABA83SWl3fCqa_Now.png" /><figcaption>A high-level overview of our solution. Image by Author.</figcaption></figure><h4>Generating extra information with <a href="https://github.com/DasLab/arnie">ARNIE</a></h4><p><a href="https://github.com/DasLab/arnie">ARNIE</a> is a software package that wraps around 6 different libraries which can be used to generate extra information for each of the sequences:</p><ul><li><a href="https://www.tbi.univie.ac.at/RNA/#download">Vienna</a></li><li><a href="http://www.nupack.org/downloads">NUPACK</a></li><li><a href="https://rna.urmc.rochester.edu/RNAstructure.html">RNAstructure</a></li><li><a href="http://www.rnasoft.ca/download.html">RNAsoft</a></li><li><a href="http://contra.stanford.edu/contrafold/">CONTRAfold</a></li><li><a href="http://https//eternagame.org/about/software">EternaFold</a></li></ul><p>For a provided RNA sequence, ARNIE is able to calculate a Base Pairing Probability (BPP) matrix. Based on that BPP, a potential structure can be predicted and from these structures, the loop type can be inferred for each of the bases in the sequence.</p><p>We used different libraries in ARNIE to generate extra information. This often required a bit of bash magic in order to get everything installed. <a href="https://www.kaggle.com/group16/generating-bpps-with-arnie">We provide a notebook to demonstrate how to generate this information.</a> We experimented with all 6 libraries, but only found CONTRAfold to be the most useful, followed by RNAsoft, RNAstructure and Vienna.</p><h4>Node features</h4><p>From our high-level overview, we can see 2 types of inputs are required for our network: node information and edge information. The node information is a NxLxV matrix with N the number of RNA sequences, L the length of the sequences and V the number of features per node. We use V=25 features in total:</p><ul><li>One-hot-encoded <strong>base</strong> (‘A’, ‘G’, ‘C’ or ‘U’) (4 features)</li><li>One-hot-encoded <strong>loop type</strong> (provided: ‘S’: paired Stem, ‘M’: Multiloop, ‘I’: Internal loop, ‘B’: Bulge, ‘H’: Hairpin loop, ‘E’: dangling End or ‘X’: eXternal loop) (7 features)</li><li>one-hot-encoded <strong>positional</strong> feature (index % 3) (3 features)</li><li><strong>certainty</strong>: fraction of packages (3 different ones: Vienna, CONTRAfold and RNAstructure) that predict (, ) or . (3 features).</li><li><strong>CapR loop type</strong> probabilities (6 features)</li><li><strong>BPP</strong> sum and number of zeroes (2 features)</li></ul><h4>Edge features</h4><p>The edge information is captured in a NxLxLxE matrix, with N the number of RNA sequences, L the length of the sequences and E the number of edge features. In total, we have E=5 features for each edge:</p><ul><li>3 different <strong>BPPs</strong>: the provided ones, generated with RNAsoft (ARNIE) and generated with contrafold (ARNIE)</li><li>whether there is a <strong>base pairing</strong> indicated in the structure ( ( and ) )</li><li>the <strong>distances</strong> (manhattan) between bases, normalized by sequence length</li></ul><h4>The model</h4><p>Our pipeline was an adaptation <a href="https://www.kaggle.com/mrkmakr/covid-ae-pretrain-gnn-attn-cnn">from this great notebook</a> by <a href="https://www.kaggle.com/mrkmakr">mrmakr</a>. Make sure to give that notebook an upvote! We did make a few modifications to the original notebook:</p><ul><li>Corrected the loss function of the classification part of the network.</li><li>Changed the loss function of the auto-encoder, which was tailored for binary representations (it was a variant of binary cross-entropy). We simply used Reconstruction Loss/MAE (|y — y_hat|).</li><li>Added 2 RNN layers after the Encoder. As was illustrated during the competition (by <a href="https://www.kaggle.com/tuckerarrants">@tuckerarrants</a> and others), blending a GRU+GRU, LSTM+GRU, GRU+LSTM and LSTM+LSTM model results in a slight boost. We generated models in 10-fold CV for each of these 4 combinations (so 40 models in total) and blended those with uniform weights.</li><li>Tuned some hyper-parameters. The epochs of AE, Classification part, the number of units in the GCN layers, …</li><li>Adding augmented data, from the <a href="https://www.kaggle.com/its7171/how-to-generate-augmentation-data">notebook</a> made by <a href="https://www.kaggle.com/its7171">@its7171</a>.</li><li>Training on all the samples but using different sample weights based on their signal_to_noise. Again a shout out to <a href="https://www.kaggle.com/its7171">@its7171</a> for this! Evaluation was only performed on data with SN_filter=1. Because we expected the private LB to do that as well ;)</li></ul><h4><strong>Things that did not work</strong></h4><p>We tried many things that did not work:</p><ul><li>We got 3D foldings of all the RNA and calculated 3D (euclidean) distances between the RNA bases. We also tried to use angle information (binned and then categorically encoded): this boosted our simple LSTM architecture but deteriorated the performance of the AE+LSTM. There’s definitely some potential in these features, but they require some more thorough experimentation. A dataset to allow for such experimentation can be found <a href="https://www.kaggle.com/mtinti/angles">here</a>.</li><li>Many software packages that give some RNA features were not informative. Some of these include RNAup, Shaker, MXFold, …</li><li>All of the spectral representations discussed in <a href="https://www.biorxiv.org/content/10.1101/2020.06.08.140368v1.full">this paper</a>.</li><li>Richer graph representations (e.g. including amino-acid information)</li><li>Entropy features</li><li>Atom information</li></ul><h4>Concluding words</h4><p>I really enjoyed this competition. I especially liked the fact that it only lasted for a rather short period of time. It was a neck-to-neck race on the public leaderboard for the course of the entire competition. Very stressful, but fun! This kind of “blitz” competitions could perhaps be considered as a separate format by Kaggle?</p><p>While we just missed out on the money (by 1 position), we are still very proud of our result! With this result, my two teammates: <a href="https://www.kaggle.com/bsteenwi">Bram</a> and <a href="https://www.kaggle.com/mtinti">Michele</a> have also become Kaggle Competition Masters. So a huge congratulations to them!</p><p>We provide the code of our solution on both <a href="https://www.kaggle.com/group16/covid-19-mrna-4th-place-solution">Kaggle</a> and <a href="https://github.com/GillesVandewiele/covid19-mrna-degradation-prediction">Github</a>.</p><p><strong>As usual, if anything is unclear or requires some more explanation: do not hesitate to leave a comment or contact me!</strong></p><p><strong>Keep an eye open on this post, as it may receive some updates in the nearby future!</strong></p><p>See you in the next competition!<br>Gilles, Bram and Michele</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b3070d20b2e5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/predicting-mrna-degradation-using-gnns-and-rnns-in-the-search-for-a-covid-19-vaccine-b3070d20b2e5">Predicting mRNA Degradation using GNNs and RNNs in the Search for a COVID-19 Vaccine</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Identifying the Number of Open Ion Channels with Hidden Markov Models]]></title>
            <link>https://medium.com/data-science/identifying-the-number-of-open-ion-channels-with-hidden-markov-models-334fab86fc85?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/334fab86fc85</guid>
            <category><![CDATA[time-series-analysis]]></category>
            <category><![CDATA[competition]]></category>
            <category><![CDATA[hidden-markov-models]]></category>
            <category><![CDATA[kaggle]]></category>
            <category><![CDATA[signal-processing]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Tue, 26 May 2020 15:52:00 GMT</pubDate>
            <atom:updated>2020-06-04T11:58:30.723Z</atom:updated>
            <content:encoded><![CDATA[<h4>A write-up on how we almost won the “University of Liverpool — Ion Switching” Kaggle competition</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ff56t2S6j-pywr60QDkKIA.png" /></figure><p><a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching"><strong>EDIT 04/06/2020: We have now released our code!</strong></a></p><p>On the 24th of February, <a href="http://www.kaggle.com/">Kaggle</a> released a new “Research” competition, with a prize pool of $25,000, in collaboration with the <a href="https://www.liverpool.ac.uk/">University of Liverpool</a>. In this competition, we were provided with electrical signals corresponding to ion channel data, and our goal was to create an algorithm that could automatically identify the number of channels that were open at each time point. Initially, the competition launched with an exotic “Quadratic Weighted Cohen Kappa Score (QWK)”, but this resulted in near-perfect results a few moments after release, which made <a href="https://www.kaggle.com/c/liverpool-ion-switching/discussion/132527">me reluctant to join</a>. After a while, the competition metric changed to a more reasonable macro F1-score, after which it was clear that we were still far away from a perfect solution. I decided to join because of several reasons:</p><ul><li>It is timeseries data.</li><li>It is only one single timeseries, which allows us to focus more on pre-processing and modelling rather than feature engineering.</li><li>The dataset was rather small, with a total of 5 million measurements in the training set and 2 million measurements in the test set. The total storage needed was around 125 MB.</li></ul><p>I had the honor to team up with two of the brightest people I ever had a chance of working with: <a href="https://www.kaggle.com/khahuras">Kha Vo</a> and <a href="https://www.kaggle.com/zidmie">Zidmie</a>. <strong>In the end, we managed to secure ourselves the third spot and $5,000 and came out on top of over 2600 teams. </strong><a href="https://www.kaggle.com/c/liverpool-ion-switching/discussion/153824">The number one and two managed to find a leak in the private test data</a> towards the end of the competition that we did not discover (only right after knowing of its existence). One other way to re-phrase this, is that we had the <strong>best non-leaky solution</strong>! In the end, we were able <a href="#cf75">to find this leak ourselves</a> in a short amount of time, which makes it even more frustrating…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/758/1*V10hsLxhpun-sNbcF0dqgQ.png" /></figure><p>This blog post will provide a detailed overview of our solution, and provides the insights that were required for us to come up with our solution. Below is a table of contents:</p><ul><li><a href="#d423"><strong>Introduction</strong></a><br>- <a href="#da77">Problem Statement</a><br>- <a href="#08e4">A look at the data &amp; competition metric</a></li><li><a href="#634a"><strong>Pre-processing</strong></a><br>- <a href="#2d98">Pre-processing I: removing drift</a><br>- <a href="#9466">Pre-processing II: linear transformation</a><br>- <a href="#5270">Pre-processing III: power line interference removal</a><br>- <a href="#cf75">Category 5 = Category 4 + Category 4</a></li><li><a href="#5857"><strong>Modeling</strong></a><br>- <a href="#2e4c">Hidden Markov Model: 1-channel data</a><br>- <a href="#2bb4">“Hidden” Hidden Markov Model</a><br>- <a href="#8d9f">Extending Hidden Markov Models to K-channel</a><br>- <a href="#2bfb">Introducing memory in Hidden Markov Models</a></li><li><a href="#fe33"><strong>Post-processing</strong></a><br>- <a href="#2b73">Post-processing the posterior probabilities</a><br>- <a href="#0a56">A bit of blending</a></li><li><a href="#0d40"><strong>Conclusion</strong></a></li></ul><h3>Introduction</h3><h4><strong>Problem statement</strong></h4><p><a href="https://en.wikipedia.org/wiki/Ion_channel">Ion channels</a> are pore-forming membrane proteins, present in animals and plants, that allow ions to pass through the channel pore. They encode learning and memory, help fight infections, enable pain signals, and stimulate muscle contraction. These ion channels can be recorded through <a href="https://en.wikipedia.org/wiki/Patch_clamp">patch clamp techniques</a> and analyzed to infer certain properties of diseases.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/290/0*HIIcIbkyZt-SB3YQ.png" /><figcaption>Schematic diagram of an ion channel from <a href="https://en.wikipedia.org/wiki/Ion_channel">Wikipedia</a>.</figcaption></figure><p>The organizers describe the challenge as follows: “When ion channels open, they pass electric currents. Existing methods of detecting these state changes are slow and laborious. Humans must supervise the analysis, which imparts considerable bias, in addition to being tedious. These difficulties limit the volume of ion channel current analysis that can be used in research. Scientists hope that technology could enable rapid automatic detection of ion channel current events in raw data. Technology to analyze electrical data in cells has not changed significantly over the past 20 years. If we better understand ion channel activity, the research could impact many areas related to cell health and migration. From human diseases to how climate change affects plants, faster detection of ion channels could greatly accelerate solutions to major world problems.”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/0*6j-rZexieclEBDEy.jpg" /><figcaption>We can clearly see an increase in our current when ion channels open.</figcaption></figure><h4>A look at the data &amp; competition metric</h4><p>The data provided to us is rather simple, which is one of the nice things about this competition. The data contains only three columns:</p><ul><li>A timestamp</li><li>Ampere values (current) for each timestamp. These values were measured at a sampling frequency of 10 kHz.</li><li>The corresponding number of open channels at that timestamp (only provided for the train data).</li></ul><p>The training dataset consists of 5 million rows while the testing dataset consists of 2 million rows. The goal of the competition is to maximize the macro F1-score on those 2 million rows. The F1 score of a certain class is defined as the harmonic average of the precision and recall:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*HWciPNLkZkWQj7nwq91HRw.png" /></figure><p>The <strong>“macro” </strong>F1 is simply the average F1 score per class. So if we would have <em>K</em> classes, we would calculate <em>K</em> F1 scores and then take the mean of those <em>K</em> scores. If we inspect the provided data, we can already conclude a few interesting things…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*r3shxOo2LsF-bAh85DVtEQ.png" /><figcaption>The provided original data (train and test)</figcaption></figure><p>First, by inspecting the open channels in the training data, we can see that the <em>data consists of batches of 500K measurements</em>. We can see these transitions in batches in the electrical signal as well. In the test set, we can find <em>batches of 100K</em>. Moreover, as it turns out, the batches of 500K in the training set actually consist of 5x 100K batches.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*HVX4NzoE__QLqXnZ.png" /><figcaption>The training consists of multiple batches of 500K. Taken from <a href="https://www.kaggle.com/cdeotte/one-feature-model-0-930">“One Feature Model”</a> by <a href="https://www.kaggle.com/cdeotte">Chris Deotte</a>.</figcaption></figure><p>By inspecting the open channels in the training set more, we can find five different groups in the training set:</p><ul><li>A group with open channels either equal to 0 or 1. With many 0’s and a few 1’s. <strong>(category 1)</strong></li><li>A group with open channels equal to 0 or 1. Many 1’s, few 0’s. <strong>(category 2)</strong></li><li>A group of open channels equal to 0, 1, 2, 3. <strong>(category 3)</strong></li><li>A group of open channels equal to 0, 1, 2, 3, 4, 5. <strong>(category 4)</strong></li><li>A group of open channels equal to 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. <strong>(category 5)</strong></li><li>Surprisingly, the test data contained a lot of data that looked very similar to category 1, but had some spikes in the electrical signal that do not appear in the train data. Hence, we classify these as a separate category <strong>(category 6)</strong></li></ul><p>When combining this insight with the competition metric, it becomes clear that <em>the group with up to 10 open channels </em><strong><em>(category 5)</em></strong><em> will have the largest impact on the macro F1 average.</em> It has 5 unique classes (6, 7, 8, 9, 10) that do not appear in other groups, as such, this group of data contributes for more than 50% to our macro F1 score. During the course of the competition, <a href="https://www.kaggle.com/waylongo">Waylon Wu</a> <a href="https://www.kaggle.com/c/liverpool-ion-switching/discussion/133142">discovered</a>, by probing, that the public LB consisted of the first 30% (or 600000) test values, while the private LB consisted of the remaining 70% (1400000).</p><h3>Pre-processing</h3><h4>Pre-processing I: removing drift</h4><p>We noticed that weird drift is present in the beginning and in the end of our training signal, and in different places of the test signal… We notice two types of drift: curved drift (e.g. in the end of the training signal) and linear drift (e.g. in the start of the training signal, around time=50).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/492/1*BeNRo1oOChFq6M16zTy0Vg.png" /><figcaption>Two subsamples from the signal illustrating the two types of drift.</figcaption></figure><p>In the end, it turned out that the “linear” drift was not linear at all, but was actually just a small part of the “curved” drift (e.g. the first half of our curved drift looks linear as well). Shortly after the start of the competition, <a href="https://www.kaggle.com/eunholee">Eunho Lee</a> and <a href="https://www.kaggle.com/friedchips">Markus F</a> discovered that the competition organizers introduced artificial noise in the data, by using a <a href="https://www.kaggle.com/eunholee/remove-drift-using-a-sine-function">sine function with a very low frequency</a> (with a period of 1.000.000 values). <a href="https://www.kaggle.com/cdeotte">Chris Deotte </a>bundled the insights from the two independent analysis to perform the cleanest drift removal and <a href="https://www.kaggle.com/cdeotte/data-without-drift">make a dataset out of it</a> that could be used by all other competitors (thanks Chris!). Our new data now looks as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MOpf986ZhNr02-GTHd6Rwg.png" /><figcaption>The data after drift removal</figcaption></figure><p>We can notice that something is still going wrong from time=360 until time=390. We decided to not bother about this, since such an anomaly was not present in the test set, and we removed this data from our training set.</p><h4>Pre-processing II: linear transformation</h4><p>By inspecting the data, it becomes clear that the train signal and number of open channels are extremely correlated. As a matter of fact, applying a linear transformation on the electrical signal and then rounding the resulting values already performs rather well.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*oQei2zhpLI55h16mKTw53w.png" /><figcaption>The electrical signal and the number of open channels are heavily correlated.</figcaption></figure><p>We decided to learn a linear transformation per category of data that best maps the electrical signal values to the number of open channels, this allowed easier analysis in future steps. The transformation is rather simple, we learned two different parameters for the following function (1D Linear Regression):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/309/0*X0p4yvxk4QEV4Q2U" /><figcaption>1D Linear Regression to better align the electrical signal (x) with its respective number of open channels. o is the offset and s is the slope of our linear regression.</figcaption></figure><p>Our slope was the same for each category (0.8107) and the offset was dependent on the categories (2.221318 for categories 2, 3, 4 and 6; 4.4288541 for category 5 and 2.180783 for category 1)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*77gUhYIK9fF4uerdS7fDGA.png" /><figcaption>The aligned data. Notice how the electrical signal now already corresponds very well the respective number of open channels. Rounding the signal values would result in a strong baseline already.</figcaption></figure><p><a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/1%20-%20Align%20Channels%20and%20Signal.ipynb">We provide a notebook with python code that illustrates this.</a></p><h4>Pre-processing III: power line interference removal</h4><p>As I mentioned in the previous section, rounding our aligned electrical signal values would already result in a strong baseline. Unfortunately, it would not result in a perfect score… That is due to the fact that noise is present in our dataset (luckily, or this would have been quite a trivial challenge)! We can inspect this noise by simply calculating the following:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/924/0*LXgbNe5eof62lRdF" /></figure><p>Below is a plot of the first 10000 noise values of our training set:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aPsnamNFcxwULwrYckIRQA.png" /><figcaption>The first 10000 noise values of our training set</figcaption></figure><p>While it may be hard to see with the eye, there is somewhat of a wave pattern present within our noise. This becomes even more clear if we take a moving average with a centered window of size 50:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qIIesVf_EAE3tZ7Fee-FDQ.png" /><figcaption>A moving average (centered window of size 50) of our 10000 noise values.</figcaption></figure><p>We can clearly see a wave with a peak every 200 values on average. A periodic signal, measured at a sampling frequency of 10 kHz, with a period of around 200, corresponds to a frequency of 50 Hz. It turns out that the AC power in the UK (competition is by Uni of Liverpool) has a frequency of 50 Hz! In order to remove this pattern from our noise, we decided to fit a sine function on each batch of 100000 noise values (you can use <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.curve_fit.html">scipy.optimize</a> for that). While signal processing techniques, such as bandpass and bandstop filters can do this for you as well, we had better results with a simple sine function. It also turned out that having multiple components in the sine function (i.e. multiple sine waves with different amplitudes, phases and frequencies) worked the best.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*TeUQ1qDI3X1etGtS-Wrg0g.png" /><figcaption>10000 noise values and the corresponding fitted sine function.</figcaption></figure><p><a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/2%20-%20Remove%20Power%20Line%20Interference.ipynb">Again, a notebook is provided to demonstrate this with python code.</a></p><h4>Category 5 = Category 4 + Category 4</h4><p>It seemed that our noise removal technique worked really well for all categories, except for one… There was something unique about the data in category 5 that distinguished it from all the rest. By doing some experimentation, we noticed that we could mimic data from category 5 very well by just adding two random batches from category 4 together.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1SuVZ9D2vnW7Xtix9_dH7A.png" /><figcaption>Generating synthetic data of category 5 by adding two batches of category 4 together.</figcaption></figure><p>By making this assumption, we can also assume that the noise in cat 5 is the addition of two sine functions. Moreover, this insight allows for data augmentation which could be useful for, e.g., neural networks.</p><p><strong>As it turns out, this insight was actually the leak as well. We did not pursue this avenue long enough, but the private test data was EXACTLY the sum of two category 4 batches, of which one can be found in the TRAINING set... After the competition, my teammate Zidmie,</strong><a href="https://www.kaggle.com/c/liverpool-ion-switching/discussion/153824"><strong> discovered (part of) this leak</strong></a><strong> in roughly 30 minutes of looking for it (improving our private score to 0.95430). A bit frustrating to know that we improved our model much more in 30 minutes due to a leak than our work of 2 months. Later, he discovered the entire leak:</strong>y_test[570000:5800000] = predict(X_test[5700000:5800000] - X_train[4000000:4100000]) + y_train[4000000:4100000]<strong>. Since you are predicting category 4 data (with up to 5 channels) now, it becomes a much easier task.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/951/1*lbhvwQWi5DAvbZNJ5nLnNQ.png" /><figcaption>Reproducing the leaks used by #1 and #2. #1 extracted X_train from X_test while #2 extracted y_train from X_test. Extracting X_train is better than y_train, because you also reduce the noise by half!</figcaption></figure><h3>Modeling</h3><h4>Hidden Markov Model: 1-channel data</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/802/1*-H853VcrN1aab5AFZ3eXDQ.png" /><figcaption>This meme was too good of a fit to not be using it. In the end, <strong>it turned out that a leak in the private test data was the actual winner </strong>(perhaps I should create a new meme…).</figcaption></figure><p>Sequential state space models, such as Hidden Markov Models, were the state-of-the-art for a long time for these types of problems. It is only more recently that deep learning variants have been proposed (e.g. <a href="https://www.nature.com/articles/s42003-019-0729-3">this paper</a> by the competition organizers), as these are often more robust against things such as drift. Since we are pre-processing our data to remove all artifacts, we decided to go for Hidden Markov Models are our modeling technique in this competition.</p><p>There are many great introductions to Hidden Markov Models out there, so I will not go much in detail here. All we need to know is that there are different parameters that belong to each Hidden Markov Model:</p><ul><li>The number of hidden states (= K)</li><li>Initialization probabilities (vector of size K)</li><li>A transition matrix (K x K matrix)</li><li>Emission probabilities. Each hidden state emits a certain observable value. These emissions can have different distributions such as a multi-nomial for discrete emissions and a Gaussian for continuous emissions (which we are going to use here, since our electrical signal is continuous).</li></ul><p>In short, the open channels (hidden variables) follow a certain Markov Process and transit from one value to the other with certain probabilities that are determined by the transition matrix. When the Markov Process is in a certain hidden/latent state, it emits an observable value, which is the electrical signal here.</p><p>As an example, we are going to focus on category 2 which has a binary response variable (open channels = 0 or 1), and assume our Markov Model to have 2 hidden states. A hidden state for when the number of open channels is equal to 0 and one hidden state for when it is equal to 1. We can estimate both the transition matrix &amp; the emission distributions easily by looking at our training data (i.e. count transitions from one state to the other and look at signal values corresponding to a certain number of open channels):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/910/1*zBfxc_ZCuDv9AnzACgF4hQ.png" /><figcaption>The estimated Gaussians and transition probabilities for category 2 of our training data.</figcaption></figure><p>This means that, for example, if the number of open channels equals to 1, the signal value will be around 1 as well (with a bit of variance). The next value will be equal to 1 with a probability of 93.6% or 0 with a probability of 6.4%. These parameters can be estimated by using the training data, as illustrated above, but also by applying the <a href="https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm">Baum-Welch algorithm</a>. This algorithm is a special case of the Expectation-Maximization algorithm, which is an <strong>unsupervised algorithm </strong>(no cross-validation was needed which allowed faster iterations). In a nutshell (and simplistic way), it will make predictions based on its initial parameters and then use these predictions to update the parameters until convergence. Once the parameters are learned, we can perform inference by applying one of two algorithms:</p><ul><li><a href="https://en.wikipedia.org/wiki/Viterbi_algorithm">The Viterbi Algorithm</a> — which will return the most likely sequence</li><li><a href="https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm">The Forward-Backward Algorithm</a> (or Maximum A Posteriori) — returns a TxK probability matrix P where P[t][k]will be the probability of being in hidden state k at time t .</li></ul><p><a href="https://www.kaggle.com/group16/lb-0-936-1-feature-forward-backward-vs-viterbi">Initial experiments</a> already showed that the Forward-Backward algorithm worked slightly better (albeit slower) than the Viterbi. Note that these algorithms are also used in the Baum-Welch algorithm. A great library to apply all these algorithms in Python is <a href="https://hmmlearn.readthedocs.io/en/latest/">hmmlearn</a>.</p><p>Let’s fit a 2-state HMM on our pre-processed data of category 2:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/55e2c722adeb924582999c2a6101f47b/href">https://medium.com/media/55e2c722adeb924582999c2a6101f47b/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*dFI8ah7uiBClf67EbcVvVg.png" /><figcaption>The output of our script. The hmmlearn library performs the Baum-Welch algorithm for 5 iterations to adapt our parameters, after which it converges. The F1 score on this category of data is equal to 0.9961</figcaption></figure><p>So by using this rather simple approach, we can already achieve a F1 score of 0.9961 on category 2 of our data. It should be noted that categories 1 and 2 of our data are by far the easiest ones, with near-perfect performance. The F1 scores quickly drops in function of the maximum number of open channels. As an example, we cannot reach an F1 score of 0.9 on category 5 of our data. <a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/3%20-%20Fit%204-state%20HMM%20(Cat%203).ipynb">Please see this notebook for a more elaborate example.</a></p><h4>“Hidden” Hidden Markov Model</h4><p>When reading a paper published by the organizers, it becomes clear that while the number of open channels follow a Markovian Process, they are in turn generated by a Hidden Markov Model.:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*NL2Ido9Rki_oidEc.png" /><figcaption>The ground truth (open channels) is generated by a Markov Process, this can either by synthetic (which was the case for this competition) or real (as it is assumed that real ion channels do follow a Markov process). This ground truth was then played through patch clamp amplifier and recorded back, which generated our observable data with noise (the electrical signal). <a href="https://www.nature.com/articles/s42003-019-0729-3/figures/1">Figure taken from a paper by the organizers.</a></figcaption></figure><p>This Hidden Markov Model consists of more hidden states than the number of unique open channel values. This was <a href="https://www.kaggle.com/c/liverpool-ion-switching/discussion/140634">pointed out</a> during the competition by <a href="https://www.kaggle.com/friedchips">Markus F</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/731/1*MZJdMmSWQOmda0Cld0RUrQ.png" /><figcaption>A “vanilla” HMM on the left, and a 2-layer or Hidden Hidden Markov Model on the right.</figcaption></figure><p>A simple way to approach this, is by ignoring the middle layer (y(t)) in our 2-layer model. As such, we have a Hidden Markovian Process with a number of hidden states larger than the number of unique open channels. Let’s apply this insight to our category 2 data. We will use 4 hidden states in our HMM (we have experimented with other numbers, but 4 worked best). The first two hidden states will correspond to when the number of open channels is equal to 1, the 2 following hidden states correspond to when the open channels is 0. Estimating the initial transition matrix now becomes more difficult as we cannot directly estimate it from our training data, we tuned the transition matrix manually.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/21cce218bf9aadbef45376579d097994/href">https://medium.com/media/21cce218bf9aadbef45376579d097994/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*ZcYx2VCKnY5sdHn-uGZuOA.png" /><figcaption>The output of our script. Notice how the negative log-likelihood, which is being printed by hmmlearn during the iterations, is twice as large as the log-likelihood with 2 hidden states.</figcaption></figure><p>As can be noticed, we now achieve a F1 score of 0.9972, which is an increase of roughly 0.001 as opposed to using only 2 hidden states. This improvement is very significant, especially considering the fact that this improvement increases even more with higher numbers of open channels. A difference of 0.001 in F1 scores is the difference between a silver and gold medal in the end. The F1 can probably be improved even more by introducing more hidden states or by adjusting the initial transition matrix, but a smaller transition matrix had several advantages, which will be more clear later. <a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/5%20-%20Fit%2020-state%20HMM%20(Cat%203).ipynb">Python code for this can be found in this notebook.</a> For more information on how we manually tuned the transition matrix, we refer the reader through to <a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/4%20-%20Setting%20the%20Transition%20Matrix.ipynb">this notebook.</a></p><h4>Extending Hidden Markov Models to K channels</h4><p>It seems that we can very accurately model category 1 and 2 of our data, which has up to 1 open channel. The question (of $25,000) is now whether we can apply this approach to the other categories of our data with more than 1 open channel. It turns out that this is far from a trivial case… Designing a large initial transition matrix and determining which hidden states correspond to which numbers of open channels is hard and expensive (our search space is infinitely large actually).</p><p>As such, we made the assumption that when the maximum number of open channels in a batch of data equals K that we are then dealing with K independent binary Markovian processes. Moreover, each of these Markovian processes have very similar parameters as category 2 of our data. Having several independent hidden processes resulting in an observable variable is a perfect fit for <a href="http://www.ee.columbia.edu/~sfchang/course/svia-F03/papers/factorial-HMM-97.pdf">Factorial Hidden Markov Models</a>. Unfortunately, we did not find a good library in Python (there’s <a href="https://github.com/regevs/factorial_hmm">factorialHMM</a>, which is a great package, but we did not get it working quickly enough during the competition and there’s <a href="http://pyro.ai/">Pyro.ai</a> but the learning curve is very steep (at least to me)).</p><p>With no implementations available, we realized that it was going to be a difficult and long process to implement this ourselves. We therefore decided to “hack” our way around the aspect of independent processes, by converting the smaller transition matrices, used to model data up to 1 open channels, into larger transition matrices. Each of the hidden states in our new large Markov process corresponds to the possible combinations of hidden states in the independent processes. The order does not matter (i.e. (0, 2) (which means that 1 process is in hidden state 0 and the other in hidden state 2) is the same as (2, 0)). This construction is done recursively as illustrated below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YYCzMIwujJPGYCc7G4r7WA.png" /><figcaption>In order to model 2 independent processes, we first extend our 4 hidden states to 16 hidden states that capture all possible combinations of hidden states. Afterwards we group similar states together (marked with same color). We could then continue further to model 3 processes by expanding our new 10x10 matrix into a 40x40 and reducing it back to a 20x20 (and so on). <strong>There are transitions between all states in the Markov Chain (I just did not draw all of them).</strong></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/551/1*vXSSZos4qva0co4EpAlENg.png" /><figcaption>Expanding our 4x4 transition matrix to model independent processes.</figcaption></figure><p>In each iteration, we first expand our transition matrix. If the initial transition matrix is N x N, then our newly expanded matrix will be N*K x N*K which capture all possible interactions of our N initial states with K new possibly states. When there are 2 independent processes, an example would be that process 1 is in hidden state 0 and process 2 in hidden state 1. After this expansion, we group similar states together (such as the green cells in our figure). Using our example, process 1 being in hidden state 0 and process 2 in hidden state 1 is equivalent to process 1 being in hidden state 1 and process 2 in hidden state 0. Our newly generated matrix will be of dimensions C x C after this procedure, with C equal to the number of combinations with repetition, from P independent processes out of K possible states. As an example, with 4 hidden states and 3 independent processes, C would be equal to 20 (Comb_with_Repetition(4, 3) = Comb(4 + 3 – 1, 3) = 20).</p><p>Below is Python code to do this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4ee48d98bdaf7df266af6405c9b985b3/href">https://medium.com/media/4ee48d98bdaf7df266af6405c9b985b3/href</a></iframe><p>It should be noted that this algorithm was not that straight-forward to implement, and that a simple (but much more readable) implementation resulted in estimated runtimes of a few weeks when the number of processes was equal to 10. It already took this implementation around 2 minutes to generate the transition matrix with 10 processes with a 4x4 initial matrix, and already much longer for a 5x5 matrix (hence why we stayed with a 4x4).</p><h4>Introducing memory in Hidden Markov Models</h4><p>We implemented the forward-backward algorithm ourselves, which gaves us a lot of degrees of freedom. We tried many different adjustments to the vanilla implementation of the algorithm, but the one that resulted in the most significant improvement was the introduction of memory. When calculating the probabilities at timestep t in the backward pass, we use the calculated probabilities at timestep t of the forward pass:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/0*k3rG36bLha9dpvIH" /><figcaption>Calculating the backward probabilities (betas). Psig is our emission probability, Ptran our transition probability, c a coefficient (the higher, the more impact the forward probabilities have).</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/0*1Hi3mNzldPVqxzXj" /><figcaption>Calculating our forward probabilities (alphas).</figcaption></figure><p>In total, we perform three passes. One forward pass, of which we use the alphas in our next backward pass and finally a last forward pass using our newly calculated betas. Our Psig is calculated as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/0*2_CfMQsWt07y3NX_" /><figcaption>Calculating our Psig uses a Gaussian distribution with a mean of 0 and a sigma which can be tuned. This results in |States| probabilities.</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/88c8585f283bca11ee3f06881e801236/href">https://medium.com/media/88c8585f283bca11ee3f06881e801236/href</a></iframe><p><a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/6%20-%20Custom%20Forward-Backward%20(Cat%203).ipynb">A working example of this custom forward-backward algorithm can be found here.</a></p><h3>Post-processing</h3><h4>Post-processing the posterior probabilities</h4><p>After our forward backward algorith, we are left with a TxK with probabilities for each possible hidden state and each timestep. As we have multiple hidden states that correspond to the same value of open channels, we need another post-processing step to convert these probabilities into predictions. As a first step, we took the dot product of our K probabilities in each timestep with our K states, which is the same as a weighted sum and thus results in a continuous value Y. We then decided to learn thresholds for each class and each category of data. If Y falls between two thresholds, then it is assigned to the corresponding class.</p><p>To determine these thresholds, we used somewhat of an unsupervised technique. First, we filtered out the signals that were close to their rounded value (as not a lot of noise was present in these) and used their rounded values as labels. Then, we determined the distribution of these rounded values and picked the thresholds such that it would produce a similar distribution.</p><p><a href="https://github.com/GillesVandewiele/Liverpool-Ion-Switching/blob/master/notebooks/7%20-%20Prediction%20Post-Processing%20(Cat%203).ipynb">Please check out this notebook with our post-processing code.</a></p><h4>A bit of blending</h4><p>Many variants of this HMM have been made in the course of this competition. My teammate Zidmie used a counter in his scripts, and he was at 342 in the end (so 342 different scripts have been written by himself only). Throughout the course of the competition, we kept marginally improving both our CV and public LB score. Often, the number of differences between consecutive versions were a lot higher than the differences in CV scores, which means that not all of the changes made by the new version were actually correct. We therefore blended different outputs of our forward-backward algorithms together (by using their calculated probabilities). This gave us some marginal increases.</p><h4>Concluding notes</h4><p>I am extremely proud of our final result. I think the solution is rather elegant, given that it is not the typical ensemble of 1001 different models that you often see on Kaggle and that it runs in less than one hour. We also never used the code of the competition organizers to create extra data or to reverse engineer the data generation process. In the end, I was a bit disappointed to drop two spots due to a leak that was discovered by other teams and not by us. Nevertheless, I learned a whole lot during this competition as I never used a Hidden Markov Model before and got to know 2 great and bright people!</p><p>Keep an eye on this page, as it probably can/will receive minor updates over the next few days. Also, we are working towards releasing our code!</p><p>Thank you again <a href="https://www.kaggle.com/khahuras">Kha Vo</a> and <a href="https://www.kaggle.com/zidmie">Zidmie</a> a lot of fun during this competition!</p><p><strong>Acknowledgements:</strong> the authors would like to thank <a href="https://www.kaggle.com/marcogorelli">Marco Gorelli</a> for his constructive feedback.</p><h4>Sources</h4><ul><li><a href="https://www.kaggle.com/c/liverpool-ion-switching/overview">University of Liverpool - Ion Switching</a></li><li><a href="https://en.wikipedia.org/wiki/Ion_channel">Ion channel</a></li><li><a href="https://www.nature.com/articles/s42003-019-0729-3">Deep-Channel uses deep neural networks to detect single-molecule events from patch-clamp data</a></li><li><a href="https://papers.nips.cc/paper/1144-factorial-hidden-markov-models">Factorial Hidden Markov Models</a></li><li><a href="https://github.com/hmmlearn/hmmlearn">GitHub - hmmlearn/hmmlearn: Hidden Markov Models in Python, with scikit-learn like API</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=334fab86fc85" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/identifying-the-number-of-open-ion-channels-with-hidden-markov-models-334fab86fc85">Identifying the Number of Open Ion Channels with Hidden Markov Models</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Explainable, efficient and accurate node classification in Knowledge Graphs]]></title>
            <link>https://medium.com/data-science/explainable-efficient-and-accurate-node-classification-in-knowledge-graphs-a5d3ba02c245?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/a5d3ba02c245</guid>
            <category><![CDATA[explainable-ai]]></category>
            <category><![CDATA[classification]]></category>
            <category><![CDATA[data-mining]]></category>
            <category><![CDATA[knowledge-graph]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Wed, 01 Apr 2020 15:33:29 GMT</pubDate>
            <atom:updated>2020-04-01T19:33:43.343Z</atom:updated>
            <content:encoded><![CDATA[<h4>Mining discriminative walks with MINDWALC</h4><h4>1. A richer data representation with (Knowledge) Graphs</h4><p>Graphs are data structures that are useful to represent ubiquitous phenomena, such as social networks, chemical molecules and recommendation systems. One of their strengths lies in the fact that they explicitly model relations (i.e. edges) between individual units (i.e. nodes), which adds an extra dimension to the data. We can illustrate this enrichment of data using the <a href="http://konect.uni-koblenz.de/networks/subelj_cora">Cora citation network</a>. This is a dataset contains a bag-of-words representation for a few hundred papers and the citation relations between each of these papers. If we apply dimensionality reduction (t-SNE) to create a 2D plot of the bag-of-words representations, we can see clusters (of similar research topics) arise but they overlap. If we produce an embedding with a graph network, that takes into account the citation information, we can see the clusters being better separated.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/493/1*DRp2KgNFil7DwxoTCusHAQ.png" /><figcaption>left: A t-SNE embedding of the bag-of-words representations of each paper. right: An embedding produced by a graph network that takes into account the citations between papers. source: “Deep Graph Infomax” by Velickovic et al.</figcaption></figure><p>Knowledge Graphs are a specific type of graph. They are multi-relational (i.e. there are different edges for different types of relations) and directed (i.e. the relations have a subject and object). Fortunately, we can convert the knowledge graphs to regular directed graphs, which facilitates further analysis.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1017/1*YlKuLVza7eHa9TVri3kW_g.png" /><figcaption>Converting a multi-relational directed Knowledge Graph in a regular directed graph.</figcaption></figure><h4>2. Node classification in (Knowledge) Graphs</h4><p>Graphs are increasingly being leveraged for various machine learning tasks. For example, one might recommend new friends to a user in a social network, predict the role of a person in a collaboration network, or classify the role of a protein in a biological interaction graph. In this post, we will focus on the task of <strong>node classification</strong>: we are provided with a set of labeled nodes in a graph and need to create a model that can predict the class of unlabeled nodes.</p><p>In this post, we shall use a running example where the goal is to classify researchers in their correct institution. Below I depicted 5 researchers. Their color corresponds to their institution. We can retrieve the neighbors of these nodes to expand our graph. As can be seen, the graph quickly grows in size. After 2 iterations of expanding, we can no longer intuitively visualize our graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_9DTMFVBoFIiMNzdywMxbQ.png" /><figcaption>Expanding our graph by retrieving the neighbors of our nodes. After 2 iterations, it becomes very hard to visualize the graph.</figcaption></figure><h4>3. Walks and wildcards</h4><p>Our goal is to mine walks (or paths in the graph) that are very discriminative for a certain class. We can notate a walk as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*8ThJFUz5en0Uy_7kBQfomw.png" /><figcaption>An example of walk of n hops.</figcaption></figure><p>This walk <strong>can be found</strong> in the neighborhood of “root” if it has a directed going to “v0”. From there, a directed edge between “v0” and “v1” has to exist and so on until we reach “vn”. If suddenly we can no longer traverse an edge to end up in the next hop of our walk, we say that the walk <strong>cannot be found</strong>.</p><p>Further, we introduce wildcards (“*”) in our walk. The semantics of this wildcards is that any vertex can be matched on that location:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/303/1*t4E2OQxvCk-QJKYst5oEAw.png" /><figcaption>Introducing wildcards in our walk.</figcaption></figure><p>Now this walk can be found in the neighborhood of root if it has a directed edge to a node that has a directed edge to v1. The label on the intermediary node does not matter.</p><h4>4. MINDWALC: Efficiently mining for discriminative walks</h4><p><a href="http://github.com/IBCNServices/MINDWALC">MINDWALC</a> (<strong>M</strong>ining <strong>In</strong>terpretable, <strong>D</strong>iscriminative <strong>Wal</strong>ks for <strong>C</strong>lassification of Nodes in a Knowledge Graph) is a technique that allows to efficiently mine for walks of a specific format. A walk of l hops must consists of l-1 wildcards, followed by a vertex in the end:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/228/1*1qNTpt4_x8eNP7useEMy4g.png" /></figure><p>This walk can be found in the neighborhood of root if x can be reached in l hops. Due to the format of this walk, we can introduce a datastructure that will allow to test whether such a walk can be found in a neighborhood in <strong>constant time</strong>. The datastructure is a <strong>list of sets</strong>. Each set, on index i in the list, contains the nodes that can be reached in exactly i hops. A code snippet on how this datastructure can be constructed is displayed below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/de532d154af68b8f0a2934ee9373646d/href">https://medium.com/media/de532d154af68b8f0a2934ee9373646d/href</a></iframe><p>The goal of MINDWALC is to find the walk that can maximize information gain. Information gain can be defined as the reduction in entropy resulting from partitioning the data. Entropy is a measure for uncertainty, as depicted below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/261/1*VY1VVzZAx8QcyJ3iqvXK4g.png" /><figcaption>The entropy is a measure for uncertainty. The more uncertainty, the higher the entropy.</figcaption></figure><p>Due to the fact that we can test for the presence of these specific walks in constant time, we can perform a brute-force search over all possible <strong>(depth, vertex) candidates</strong>. The depth defines the number of hops in our walk (so we will have depth -1 wildcards) and the vertex is the label of our final hop.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0F3pVAdu2H7iZOv5p51xzA.png" /><figcaption>MINDWALC allows to quickly calculate the information gain for all possible walks.</figcaption></figure><h4>5. Combining the mining algorithm with classification techniques</h4><p>Our mining algorithm can be combined with several classification techniques. First, we can apply the algorithm recursively in order to induce a <strong>decision tree</strong>. The resulting model is fully interpretable, since we can easily visualize the entire tree or highlight the taken path in our decision tree to form a prediction. We demonstrate this further in this post by inspecting and discussing an induced decision tree. Second, we can induce multiple decision trees, each with a subsample of both training entities and possible substructures, in order to form a <strong>forest</strong>. This ensemble technique often results in better predictive performances, but comes at a cost of lower interpretability and longer training time. Finally, we can decouple the modeling and mining by performing a single pass over the data to mine a collection of informative walks. These walks can then be used to create high-dimensional binary feature vectors (<strong>feature transform</strong>) that can be passed to any classification algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/921/1*W0vTGqNjJG-GPBrRykf4Xw.png" /></figure><h4>6. Explainable and state-of-the-art classification results</h4><p>We compared our technique to two black-box alternatives using four benchmark datasets. The black-box alternatives are <a href="https://madoc.bib.uni-mannheim.de/41307/1/Ristoski_RDF2Vec.pdf">RDF2Vec</a> and <a href="https://arxiv.org/pdf/1703.06103.pdf">R-GCN</a>. The properties of the four benchmark datasets are listed in the following table:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dXKWAHor6D6clHPQQMYxTw.png" /><figcaption>The properties of the four benchmark datasets used in our study. The AIFB dataset corresponds to the running example used in this post.</figcaption></figure><p>For each data set, we performed 10 runs. The average accuracy scores achieved on the test set and their corresponding standard deviations are summarized below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yJilhZCPA6L13gZUv5BobA.png" /><figcaption>The classification accuracies of the two black-box alternatives and our algorithm.</figcaption></figure><p>These results clearly show that all three of the proposed techniques are at least competitive to the current state-of-the-art for node classification in KGs. To conclude, we inspect a decision tree that is induced on the AIFB dataset, our running example of classifying different researchers:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KEAEcBbvLzaLSt8G4LUJrg.png" /><figcaption>A decision tree induced on the AIFB dataset.</figcaption></figure><p>In the root node, we find the walk <em>root -&gt; * -&gt; * -&gt; * -&gt; * -&gt; * -&gt; viewProjektOWL/id68instance</em>. When this walk can be found in the neighborhood of an instance, it can no longer be of the research affiliation <em>id4instance</em>, as this leaf does not occur in the subtree on the right. Moreover, this type of walk already demonstrates the added value of having a fixed depth, by the use of wildcards, in our walk. As a matter of fact, we could end up in an entity which is of a type <em>Project</em> in only two hops (e.g. <em>root -&gt; * -&gt; viewProjektOWL/id68instance</em>) from an instance, but this results in a lot less information gain than when six hops need to be taken. When inspecting the original KG, it appears that only two people, who are both from affiliation <em>id3instance</em>, are directly involved in the <em>Project</em> <em>id68instance</em>, or in other words where this path with only two hops could be matched. On the other hand, it appears that these two people have written quite a large amount of papers with the other researchers in their affiliation. As such, a walk that first hops from a certain person (the root) to one of his or her papers, and going from there to one of the two people mentioned earlier through an <em>author</em> predicate can be found for 45 people from affiliation <em>id3instance</em>, 3 people from <em>id2instance</em> and 2 people from <em>id1instance</em>. The remaining nodes in the right subtree from the root are less informative, since these will try to split the 5 people from both affiliation <em>id2instance</em> and <em>id1instance</em> from the 45 others.</p><h4>7. Conclusion</h4><p>This concludes this blog post on MINDWALC. MINDWALC is an algorithm that allows mining for a specific type of walks that are informative for certain (groups of) classes, in the context of node classification for Knowledge Graphs. Moreover, we show that this algorithm is a good basis for a predictive model, when used in combination with one of three different techniques proposed in this work. Experiments on four KG benchmark data sets show that our proposed approaches outperform the current state-of-the-art while, in contrast to these techniques, being completely interpretable. This is of great importance for applications situated in critical domains.</p><h4>References</h4><ol><li>Veličković, Petar, et al. “Deep graph infomax.” <em>arXiv preprint arXiv:1809.10341</em> (2018).</li><li>Schlichtkrull, Michael, et al. “Modeling relational data with graph convolutional networks.” <em>European Semantic Web Conference</em>. Springer, Cham, 2018.</li><li>Ristoski, Petar, et al. “RDF2Vec: RDF graph embeddings and their applications.” <em>Semantic Web</em> 10.4 (2019): 721–752.</li><li>Vandewiele, Gilles, et al. “Inducing a decision tree with discriminative paths to classify entities in a knowledge graph.” <em>SEPDA2019, the 4th International Workshop on Semantics-Powered Data Mining and Analytics</em>. 2019.</li><li><a href="https://github.com/IBCNServices/MINDWALC">https://github.com/IBCNServices/MINDWALC</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a5d3ba02c245" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/explainable-efficient-and-accurate-node-classification-in-knowledge-graphs-a5d3ba02c245">Explainable, efficient and accurate node classification in Knowledge Graphs</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Google Hash Code 2020: a greedy approach]]></title>
            <link>https://medium.com/data-science/google-hash-code-2020-a-greedy-approach-2dd4587b6033?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/2dd4587b6033</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[hashcode]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[scheduling]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Fri, 21 Feb 2020 14:47:41 GMT</pubDate>
            <atom:updated>2020-02-26T11:36:16.401Z</atom:updated>
            <content:encoded><![CDATA[<h4>How we obtained ranking 16/204 in Belgium and 531/10724 globally</h4><h4>Google Hash Code</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/0*cZF_LrrlByeBg80d.jpg" /></figure><p>Every year, Google organizes a programming competition called Hash Code. The goal is to solve an optimization problem in 4 hours in a team of 2 to 4 people. The competition attracts tens of thousands of competitors from all over the world. This was the first year I heard of it, so I decided to participate along with <a href="https://bsteenwi.github.io/">Bram Steenwinckel</a> and <a href="https://www.linkedin.com/in/pdcremer/">Pieter De Cremer</a>.</p><h4>Scanning books in multiple libraries</h4><p>The goal of this year was to obtain the highest score by scanning different books that were distributed over different libraries in a limited number of days. Copies of the same book could be available in more than one library. Each book was assigned a score, and points could only obtained once per book (i.e. scanning two copies of the same books will only award points once). Moreover, each library had a certain “signup” time (start-up/initiation time) and a different throughput (number of books that can be scanned per day). Only one library can be performing the signup process at each time instance, while scanning of books can be done in parallel. An example (and (non-optimal) solution):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VqrG9yxFQCdTOk4FvwLp2Q.png" /><figcaption>A simple example of the optimization problem. Books 0, 1, 2, 3, 4, 5 were assigned scores of 1, 2, 3, 6, 5, 4 respectively. The total number of points would be: points(day_0) + … + points(day_6). Day 0–2 do not award any points since no books are scanned. 4 points on day 3, 3 points on day 4, 9 points on day 5. No points are awarded on day 6, as books 2 and 3 are already scanned. Resulting in a total score of 16. This is of course not a great solution, as book 4 is never scanned and library 0 has a shorter signup time and higher throughput.</figcaption></figure><p>In total, we were given 6 different inputs/problems with varying number of characteristics (many libraries, many books, same scores for all books, no copies of books, etc.).</p><h4>First approach</h4><p>Our first approach was to assign a score to each of the libraries, which consisted of the sum of scores of the books it could scan before the deadline:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*ISzjx7XW3aM4Fdfb54w6rw.png" /><figcaption>Calculate the scores for all libraries in a single pass by taking the sum of highest book scores that can be scanned in time</figcaption></figure><p>We then started the signup process of the libraries in order of their scores (descending). This resulted in a score of roughly 15.1 million points.</p><h4>Re-calculating the scores</h4><p>The first approach was very fast, as it only performed a single pass over the libraries. Unfortunately, it did not score that well as it did not take into account important factors. One example of such a factor is the fact that only one library can be performing its signup process at each time instance. As such, we can schedule a new library to start scanning after the signup process of the previous one. We updated our code to pick the best library, and then keep track of the total signup time that has already passed:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*4xkNgWKaY2IlEXF_w80DBQ.png" /><figcaption>We now keep track of a time_total variable</figcaption></figure><p>This update achieved a score of 15.5 million. Our code was now a lot slower though, as it was quadratic in the number of libraries (assign scores to each of the libraries → pick best one →update counter → repeat). As such, we were no longer able to solve the fourth input problem, as the number of libraries was too high.</p><h4>Removing scanned books from the pool</h4><p>Another factor that is important is the fact that scanning multiple copies of the same book awards no extra points. As our code already kept track of the total time passed, we simple had to use a set to store the already assigned books in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*HIY3hnXBTq3Hh2et2nlQCg.png" /><figcaption>Our updated formula. books and assigned books are sets, \ is set difference</figcaption></figure><h4>Taking signup time into account</h4><p>The final adjustment we managed to make in time was updating the formula to calculate the average score it can achieve when taking into account the signup time, as opposed to just calculating the sum. This was very important for some problems where the number of books in each library was very low, as such they had a lot of idle time when they were done scanning all their books. In the first iteration, it would then pick the library with the highest scoring books, ignoring it’s throughput time. The final formula and the code for the final version can be found below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/546/1*c1Bv-aM1epi6ipj3FXaiOA.png" /><figcaption>Dividing by the signup time results in a significant gain</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/39adddfe5a70b7bc249d3fb77d575d6f/href">https://medium.com/media/39adddfe5a70b7bc249d3fb77d575d6f/href</a></iframe><p>This update was by far the most significant one, as it boosted our score to 26.6 million.</p><h4>Simplified faster version for Problem D</h4><p>After making all these updates, we only had about 20 minutes remaining until the end. We decided to focus on problem D, since that was only solved by our first version of our code (which wasn’t too good). By inspecting the input, we saw that the problem had some very unique properties: all libraries had the same throughput and signup time and the score for each of the books was the same. The only difference was the number of books available in the libraries. As such, we calculated our score by just taking the number of yet unscanned books in each library. This ran for about 15 minutes and with only a few minutes remaining, we managed to improve the score for problem D with 20000, giving us a score of roughly 26.8 million which puts us on ranking 16/204 in Belgium and 531/10724 globally.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8Gi8kkZBuTPpM0Mw_nSSig.png" /><figcaption>Our certificate for the qualification rounds.</figcaption></figure><h4>Lessons learned &amp; possible improvements</h4><ul><li>We inspected our input problems way too late. Each of the problems had unique properties, and your greedy approach should be tailored to those.</li><li>In order to write tailored approaches to each subproblem, you do need to have a strong basic version quickly.</li><li>Different tweaks could be made in order to improve the score even more. The number one achieved 27203691, which is only 1.5% higher than our score. Possible improvements include (i) taking into account frequencies of the books; (ii) adapting the formulas slightly; (iii) local neighborhood searching (making small adaptations to the solution to check if it improves); (iv) etc.</li></ul><p><strong>We definitely didn’t do bad at all, and it was a fun challenge! If you were part of one of the 530 teams ranking above us, or have some ideas of possible improvements definitely let us know!</strong></p><h4>Addendum: optimally solving the practice problem</h4><p>This year, a simple toy problem was provided as well to serve as a warm up for the real competition. The problem statement was simple, you get a collection of pizzas with a different number of slices for each pizza and a number M. The goal is to order pizzas such that the sum of slices is as close to (and does not exceed) M:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/785/1*9OVPYuh8lYfX2lChwa3oog.png" /><figcaption>If M would be equal to 17, then ordering pizzas S0, S2 and S3 is the most optimal solution, as that would give us a total of 16 slices.</figcaption></figure><p>It’s easy to see that this is just a rephrasing of the <strong>knapsack problem</strong>. Which is a walk in the park for powerful solvers such as Gurobi:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b7fa9c5fa2e6f9319b79d1b1b9a5c2f8/href">https://medium.com/media/b7fa9c5fa2e6f9319b79d1b1b9a5c2f8/href</a></iframe><p>We basically create an array asm with K binary variables, with K the number of pizzas. If asm[i] = 1, then that means we are ordering pizza i. The objective is that the sum of asm[i]*score[i] is as high as possible (or the difference with M as low as possible), with an additional constraint that it cannot exceed M. The script will read all files in the directory and write away the output files.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2dd4587b6033" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/google-hash-code-2020-a-greedy-approach-2dd4587b6033">Google Hash Code 2020: a greedy approach</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Enriching shapelets with positional information for timeseries classification]]></title>
            <link>https://medium.com/data-science/enriching-shapelets-with-positional-information-for-timeseries-classification-42b6009a54a8?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/42b6009a54a8</guid>
            <category><![CDATA[classification]]></category>
            <category><![CDATA[timeseries]]></category>
            <category><![CDATA[interpretability]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Sun, 09 Feb 2020 15:42:13 GMT</pubDate>
            <atom:updated>2020-02-13T10:28:54.028Z</atom:updated>
            <content:encoded><![CDATA[<h4>How a neat simple trick can boost both predictive performance and interpretability.</h4><h4>Timeseries classification</h4><p>Many real-world processes produce data over time, giving rise to temporal data or timeseries. As opposed to tabular data, neighboring observations (i.e. observations that are close in time) are highly correlated, requiring special effort when analyzing timeseries. One possible task that can be performed on timeseries is the classification of them. Example use cases include surface detection based on accelerometer data, classifying the type of electrical device based on electricity usage or classifying a leaf’s type based on contour information.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mxDbw5d9O-G_exDwbtBxug.png" /><figcaption>Detecting the surface where a robot (Sony AIBO) is walking on using the X-axis of the accelerometer data. Image taken from <a href="http://www.timeseriesclassification.com/description.php?Dataset=SonyAIBORobotSurface1">http://www.timeseriesclassification.com/description.php?Dataset=SonyAIBORobotSurface1</a></figcaption></figure><h4>Shapelets</h4><p>Shapelets are small subseries, or parts of the timeseries, that are informative or discriminative for a certain class. They can be used to transform the timeseries to features by calculating the distance for each of the timeseries you want to classify to a shapelet.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/582/0*BEO7MjsbYkIkZdxX.png" /><figcaption>Extracting two shapelets from the ItalyPowerDemand dataset in order to transform the timeseries into a 2-dimensional feature space. Each of the axis in the feature space represent the distance to one of the two shapelets. As can be seen, a nice linear separation can already be achieved using these two shapelets.</figcaption></figure><h4>Positional information</h4><p>Guillemé et al. recently published “<a href="https://link.springer.com/chapter/10.1007/978-3-030-39098-3_7">Localized Random Shapelets</a>” in which they present an approach to extract shapelets which can be used to create a feature matrix that consists of <strong>both</strong> distance-based features and location-based features, resulting in better predictive performances.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*BrYR1zjlZ3oFglKDR5SxyA.png" /><figcaption>Their presented technique will mine K shapelets in order to transform the N timeseries into a N x 2K feature matrix. This feature matrix consists of both the distance to each shapelet (d(Ti, Si)) and the location (l(Ti, Si)).</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*iEr890xnIM2_K4AkbpWMcw.png" /><figcaption>The features for each timeseries are calculated by sliding the shapelet over the timeseries and calculating the euclidean distance of the shapelets to the timeseries in each location. In the end, the minimal distance and corresponding location are returned. Specified distances and locations are purely conceptual and far from exact.</figcaption></figure><h4>GENDIS: efficiently extracting accurate shapelets</h4><p>We extended our technique, <a href="https://github.com/IBCNServices/GENDIS/">GENDIS</a> (GENetic DIscovery of Shapelets) to extract positional information in addition to the distances to the shapelets. As GENDIS is a genetic algorithm, it can optimize anything (its objective function does not need to be differentiable). As such, this required minimal effort but preliminary experiments show a significant boost in predictive performance. <strong>With this new update, GENDIS is able to extract shapelets that are very interpretable and able to achieve state-of-the-art predictive performances when fed to a machine learning classifier. Moreover, as opposed to techniques achieving similar performances, GENDIS does not need to perform a brute-force search AND the number of shapelets and corresponding lengths do not need to be tuned.</strong></p><p>Let’s demonstrate the new capabilities by creating an artificial dataset where positional information is the key discriminative property (as the pattern will be the same for both classes):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7319cdb2e17eed955f7f3405c197b0b1/href">https://medium.com/media/7319cdb2e17eed955f7f3405c197b0b1/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*mfNz0uXjM_dKGUH2o0OK1w.png" /><figcaption>The generated timeseries. The pattern is the same for the two classes. The only way to distinguish between the two classes is to use the location where the pattern is found.</figcaption></figure><p>We extract shapelets using both versions and measure the accuracy we can achieve using this single shapelet with a logistic regression classifier and default hyper-parameters. The older version was only able to achieve an accuracy of 81% while the new version achieves 100% accuracy. We also quickly compared the new version to the old version on three smaller datasets, and each time, the positional information significantly increased the accuracy.</p><h3>Gilles Vandewiele on Twitter</h3><p>As of today, GENDIS can now extract locality information as well, in addition to shapelet distances. Preliminary experiments, on 3 small datasets, show a significant accuracy boost: ItalyPowerDemand: 94.8 -&amp;gt; 95.9 MoteStrain: 82.3 -&amp;gt; 86.3 SonyAIBORobotSurface1: 91.3 -&amp;gt; 96.8 https://t.co/DXv1HeVo33</p><h4>Explainability of shapelets</h4><p>One of the most interesting properties of shapelets is that they are very explainable. The extracted shapelets can easily be presented to a domain expert to show which parts of the timeseries were exactly used in order to make a decision. Moreover, by optimizing both positional and distance information of the shapelets, the extracted shapelets are more interpretable as well. Without the positional information, GENDIS and related techniques such as <a href="https://www.ismll.uni-hildesheim.de/pub/pdfs/grabocka2014e-kdd.pdf">Learning Timeseries Shapelets</a>, were able to often “hack” the positional information in there. Guillemé et al. demonstrate that in their paper:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*89_3jpCyvRGWGKmb3hYMvg.png" /><figcaption>In the upper image, we see a long timeseries (lightblue), corresponding to earthquake readings, and the shapelets learned by LS, which does not incorporate positional information, in color. The extracted shapelets do achieve excellent predictive performance, but are nowhere related to the original timeseries, making them hard to interpret (they are positioned on the location where the distance from the timeseries to the shapelet is minimal). On the other hand, the LRS, which does encode the positional information, achieves excellent predictive performance and extracts shapelets that are very related to the original timeseries (as we can see that the colored subseries closely match the original lightblue timeseries).</figcaption></figure><p>So this wraps up this short post! By extending our shapelet extraction framework to extract positional information in addition to the distances to each of the shapelets, we were able to achieve some significant gains in predictive performances with a limited effort!</p><p><strong>If you have more questions on shapelets, or you have a use case involving time series classification? Get in touch with us!</strong></p><h4>Sources</h4><p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.710&amp;rep=rep1&amp;type=pdf">Ye, L., &amp; Keogh, E. (2009, June). Time series shapelets: a new primitive for data mining. In <em>Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining</em>.</a><br>[2] <a href="https://ueaeprints.uea.ac.uk/id/eprint/40201/1/LinesKDD2012.pdf">Lines, J., Davis, L. M., Hills, J., &amp; Bagnall, A. (2012, August). A shapelet transform for time series classification. In <em>Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining</em>.</a><br>[3] <a href="https://www.ismll.uni-hildesheim.de/pub/pdfs/grabocka2014e-kdd.pdf">Grabocka, J., Schilling, N., Wistuba, M., &amp; Schmidt-Thieme, L. (2014, August). Learning time-series shapelets. In <em>Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining</em>.</a><br>[4] <a href="https://project.inria.fr/aaltd19/files/2019/08/AALTD_19_Guilleme.pdf">Guillemé, M., Malinowski, S., Tavenard, R., &amp; Renard, X. (2019, September). Localized Random Shapelets. In <em>International Workshop on Advanced Analysis and Learning on Temporal Data</em>. Springer, Cham.</a><br>[5] <a href="https://arxiv.org/pdf/1910.12948.pdf">Vandewiele, G., Ongenae, F., &amp; De Turck, F. (2019). GENDIS: GENetic DIscovery of Shapelets. <em>arXiv preprint arXiv:1910.12948</em>.</a><br>[6] <a href="http://timeseriesclassification.com/">www.timeseriesclassification.com</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=42b6009a54a8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/enriching-shapelets-with-positional-information-for-timeseries-classification-42b6009a54a8">Enriching shapelets with positional information for timeseries classification</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Helping Santa plan with Mixed Integer Programming (MIP)]]></title>
            <link>https://medium.com/data-science/helping-santa-plan-with-mixed-integer-programming-mip-1951386a6ba5?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/1951386a6ba5</guid>
            <category><![CDATA[assignment-problem]]></category>
            <category><![CDATA[linear-programming]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[kaggle]]></category>
            <category><![CDATA[santa]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Wed, 15 Jan 2020 14:49:52 GMT</pubDate>
            <atom:updated>2020-01-15T15:55:08.989Z</atom:updated>
            <content:encoded><![CDATA[<h4>A write-up on how we obtained a silver medal in the “Santa’s Workshop Tour 2019” competition organized by Kaggle</h4><p>This year, <a href="https://bsteenwi.github.io/">Bram Steenwinckel</a> and I ensured our Christmas gifts by being the 28th team (of more than 1600 participants) to deliver Santa an optimal schedule for his annual 100-day workshop. This blog post contains a problem description and the different steps we took to achieve this optimal solution.</p><p><strong>DISCLAIMER: </strong>Bram and I are, by no means, experts in optimization. Nevertheless, we had a lot of fun and learned a lot.</p><h3>Problem definition</h3><p>Each year, Santa organizes a Christmas workshop spanning 100 days, allowing 5000 families to attend it. Each of the families (consisting of a certain number of family members) can provide a list of their top 10 preferences of days that they would like to attend. As the workshop venue has only a limited capacity (there must be between 125 and 300 attendants each day), it is impossible to grant everyone their first choice. Therefore, compensations are provided to families that do not get their first pick. A family of size N, not getting their first pick would get:</p><ul><li>$50 gift card if they get their second choice</li><li>$50 gift card and 25% discount (valued at $9) on Santa’s buffet per family member if they get their third choice</li><li>$100 gift card and 25% discount (valued at $9) on Santa’s buffet per family member for the fourth choice</li><li>$200 gift card and 25% discount (valued at $9) on Santa’s buffet per family member if they get their fifth choice</li><li>$200 gift card and 50% discount (valued at $18) on Santa’s buffet per family member corresponding to the sixth choice</li><li>$300 gift card and free Santa’s buffet (valued at $36) per family member for the seventh choice</li><li>$400 gift card and free Santa’s buffet (valued at $36) per family member for the eighth choice</li><li>$500 gift card, free Santa’s buffet (valued at $36) per family member, and 50% off a North Pole Helicopter Ride (value of $199) per family member if they receive their ninth choice</li><li>$500 gift card, free Santa’s buffet (valued at $36) per family member, and a free North Pole Helicopter Ride (value of $398) per family member otherwise</li></ul><p>Oh boy, I wouldn’t mind not getting a pick from my top 10 list. I can already imagine myself sitting next to Santa for a helicopter ride over the North Pole. Also, $500 and a free dinner is not too shabby.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*9SRbsY4k-WIhvWP6.jpg" /><figcaption>Uncolored image of Stevens family getting assigned its 10th choice.</figcaption></figure><p>But that’s not all… There’s also an accounting penalty if we do not uniformly distribute the number of attendants over the 100 days:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ykrhUhuNEqcB5e_T4uHaTQ.png" /><figcaption>The accounting penalty for not uniformly distributing the number of attendants. N_d is the number of attendants for day d and N_(d+1) the number of attendants on day d + 1</figcaption></figure><p><strong>The ultimate goal is to create an assignment of these 5000 families to one of the 100 days that minimizes the sum of the preference and accounting costs.</strong></p><h3>Inspecting the data &amp; costs</h3><p>Let’s take a closer look at the provided data of the 5000 families. First, let’s check the family sizes:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/1*2OrvhO_rVjNX1Eu2b8TNWQ.png" /><figcaption>The sizes of the 5000 families follow a somewhat normal distribution</figcaption></figure><p>So it seems that the family sizes are somewhat normally distributed with a size of 4 being the mode. Now let’s look at the days provided as first choice:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*elbKJFrbFSwM4iTyN4jHgg.png" /><figcaption>The number of families that provided a certain day as first choice.</figcaption></figure><p>Clearly, day 1 is a very popular one. Actually, the days count backwards, day d means d days before Christmas. As such, day 1 is the day right before Christmas, which explains why it is so popular. Moreover, we see periodical peaks corresponding to weekends. Let’s create a heatmap of the (logarithm of the) preference costs in function of the family size and assigned choice:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*I6Xg-pq6G5coRUmc_AWuZQ.png" /><figcaption>A heatmap of the preference costs in function of the family’s assigned choice and its size</figcaption></figure><p>Finally, let’s take a look at a heatmap for the log of the accounting costs:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/1*ciOmT6wp-p_hBLr13BSpFQ.png" /><figcaption>The accounting cost is always zero when the number of attendants is equal to 125 for that day and is maximal when the number of attendants on the current day is 300 and 125 the next day.</figcaption></figure><h3>First approaches: greedy, Hungarian method, genetic algorithms and simulated annealing</h3><h4>Greedy algorithm</h4><p>Our first attempt was a very naive one. As the number of attendants each day had to be at least 125, we kept a list of days that did not yet have 125 attendants. We then iterated over each of the families and assigned it to one of its choices that is still in the list. If none of the family’s choices is within that list, we just assigned it to the best choice, ensuring the attendants on that day would not exceed 300.</p><h4>Hungarian method</h4><p>Shortly after the launch of the competition, a <a href="https://opensourc.es/blog/kaggle-santa-2019">blog post</a> was published by opensourc.es which achieved a much better score than what we currently were achieving. His strategy was to ignore the accounting cost, and minimize the preference cost by using the Hungarian method. The vanilla implementation tries to uniformly assign the families (50 per day). We quickly extended that approach by assigning more families to more popular days. We actually tried to solve the following optimization problem for a while: find a 100-dimensional vector <strong>V</strong> of which the elements sum to 5000 (number of families) that results in a minimal cost when provided to the Hungarian algorithm. <strong>V</strong>[i] would then be the number of families assigned to day i. Unfortunately, this what somewhat of an “expensive” problem, for each new <strong>V</strong>, we had to re-run the Hungarian method which took some time. With our final vector, a score of <em>95441</em> was achieved as opposed to the <em>144287</em>, achieved by the original proposal. A code snippet for this can be found below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c8a971c72620191de6c03f1f05f5d9ba/href">https://medium.com/media/c8a971c72620191de6c03f1f05f5d9ba/href</a></iframe><h4>Greedy local searching</h4><p>We then implemented some algorithms (or used some of the great implementations provided to us through public notebooks) to make small adaptations to a solution. After each adaptation, we then re-calculated the score and checked if there was an improvement. It is clear that a fast scoring function is of key importance. We will discuss that further. The strategies we used were:</p><ul><li>Try moving a family to one of its choices.</li><li>Try swapping two families (take a family (=f1), pick one of its choices (=d1), then pick a second family (=f2) that is currently assigned to d1 and assign it to one of its choices (=d2)).</li><li>Similar to above but with three families.</li><li><a href="https://www.kaggle.com/golubev/c-stochastic-product-search-65ns">Stochastic Searching</a>: take a number of families (=F), and brute-force the assignment of their top-K choices. This is K**F adaptations per iteration. <strong>This strategy turned out to work best.</strong> Towards the end of the competition, a <a href="https://www.kaggle.com/golubev/c-stochastic-product-search-65ns">C++ implementation</a> of this algorithm was made available.<br> → If we feed our 95441 solutions created by the Hungarian method to this algorithm, we can obtain a score of around <em>75000</em> after 45 minutes.</li></ul><h4>Genetic Algorithms &amp; Simulated Annealing</h4><p>We also played around a bit with some meta-heuristics. Our first thought was that genetic algorithms would excel in this competition. We focused on genetic algorithms quickly after the beginning of the competition, but quickly gave up on it as our population always converged to a very bad score. Simulated annealing was more successful, as it sometimes helped us to escape out of a local minimum where our greedy local searches could not escape from. The gist of simulated annealing is that it allows a solution to temporarily worsen, in order to escape a deep local optimum.</p><h4>Fast calculation of the cost</h4><p>As mentioned, a fast cost function is very important, as this allows for more local searching in the same time frame. People quickly provided <a href="https://www.kaggle.com/xhlulu/santa-s-2019-faster-cost-function-24-s">C implementations </a>that could be used within python that could run in a few nanoseconds. These implementations could even be optimized even more, due to the nature of local searches: as the adaptations in each iteration are minimal, we do not need to calculate the preference &amp; accounting cost for every day <a href="https://www.kaggle.com/khahuras/the-elegant-prize">but only the affected ones</a>.</p><h3>LocalSolver for non-linear optimization</h3><p>As the competition was progressing, it became clear that the top competitors actually achieved the optimal score (68888.04). And as the days passed, more and more people were achieving that optimal value. On 6 December (which is “<a href="https://en.wikipedia.org/wiki/Sinterklaas">Sinterklaas</a>” in Belgium), the people from LocalSolver (a non-linear solver) gave us a gift. They <a href="https://twitter.com/localsolver/status/1203002028282257409">tweeted</a> a dumbed-down version of their solution to achieve a top 50 position, using their tool. The solution was a formulation of the non-linear objective, which could be optimized with their tool. We got ourselves an academic license and ran the tool, which resulted in a score of roughly <em>71000</em> at that time. A code snippet can be found below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e945de3b0012c0d2b5ec8f8b185094f8/href">https://medium.com/media/e945de3b0012c0d2b5ec8f8b185094f8/href</a></iframe><p>In a nutshell, we create a 5000x100 binary matrix <strong>x</strong> which contains the assignments of the families to the days. If <strong>x[f][d] = 1</strong>, then family f is assigned to day d. From this, a 100-dimensional <strong>N</strong>-vector is created that contains the occupancy for each day. We then place constraints that each family should be assigned exactly 1 day and that the occupancy of each day cannot be lower than 125 and not exceed 300. Using <strong>x</strong> and <strong>N</strong> we can then directly formulate our non-linear objective and let LocalSolver work his magic to find the optimal <strong>x</strong>-matrix.</p><h3>Mixed Integer Programming with Gurobi</h3><p>While using LocalSolver was a direct improvement compared to using our greedy local searches, it was still rather far away from the optimum. We therefore turned to solving a (linear) Mixed Integer Program (using Gurobi, a powerful commercial solver). To do this, we had to apply some tricks.</p><h4>Making the objective linear</h4><p>First, LP or MIP solvers expect constraints and objectives to be at most quadratic and preferably linear. When looking at the formula for the accounting penalty, it is clear that this is a non-linear function. BUT, as the occupancy of a day is restricted to be between 125 and 300, the number of inputs to this accounting function is limited. From the formula, we can see two dependent variables: the occupancy of the current day and the occupancy of day d + 1 (which is the previous day in this framework). As such, we can create a (lookup) 176x176 matrix that contain all possible values of this accounting cost (we hinted at that by creating grid lines in the heatmap of the accounting costs). In total, a 100x176x176 matrix, called <strong>occ</strong>, was used to store all this information. <strong>occ[d][k][l]</strong> was equal to 1 if on day d the occupancy was equal to k and on day d + 1 equal to l. This matrix is huge, but we can easily prune out some of the variables. We know that the accounting cost of the optimal solution is roughly 6020, as such binary variables that are associated with costs higher than this can immediately be discarded.</p><h4>Using only 10 binary variables per family</h4><p>In our LocalSolver formulation, we used a 5000x100 binary matrix to store our assignment in. When inspecting our solutions, it quickly became clear that the optimal solution would never assign a bad choice to a family. As such, we could reduce our binary matrix to be of size 5000x10. <strong>x[f][c]</strong> would then be 1 if family f gets assigned choice c.</p><p>In summary, we have the following variables:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/332/1*4NPEWFphI7IsjgTqSk7q4g.png" /><figcaption>The assignment variables</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/439/1*lzpVse9UNHry2jVRugaLEA.png" /><figcaption>The occupancy variables</figcaption></figure><p>Of course, we can also calculate the occupancy variables from the assignment matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/508/1*KT8AuYqnW7eHL58JLsd1PA.png" /><figcaption>Calculating the occupancy from the assignment matrix</figcaption></figure><p>Here, family_size contains the sizes of each of the families and choices is a matrix that contains the choices for each family. To make this more concrete, let’s look at a simple example. Assume we have 5 families with the following choice matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*SoFninQFzpxeGWyLtL5iVQ.png" /><figcaption>A simple example of a choice matrix for families</figcaption></figure><p>Then the occupancy of day 1 (occupancy(1)) would be equal to:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/817/1*-9jNjT7yWF9PqVMySB7EGw.png" /><figcaption>An example of calculating the occupancy based on the assignment matrix</figcaption></figure><p>We then add constraints that the occupancy should be between 125 and 300, that each family must exactly be assigned one of its choices and that the one bits in the binary occupancy matrix must be consistent with the calculated occupancy values. Finally, we optimize the following objective:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/424/1*yS7v5FxquCfLUluGLxz1MA.png" /><figcaption>The objective of our MIP</figcaption></figure><p>With PREF and ACC two matrices that contain the corresponding costs. The code that can be provided to Gurobi can be found below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/eadc6b635d2d9b1a1e4a67e629de0acb/href">https://medium.com/media/eadc6b635d2d9b1a1e4a67e629de0acb/href</a></iframe><p>We let this run for 1 week (!!) and it finally outputted the optimal solution. Some tricks can be added for faster convergence, most notably adding constraints that guide the solver towards the optimal solution of 68888.04 (with a corresponding “optimality proof” of the solver). <strong>If you managed to make your solver converge faster than 1 week, then please let us know in the comments!</strong></p><h4>Visualizing our result</h4><p>Using a <a href="https://www.kaggle.com/ghostskipper/visualising-results">public kernel</a>, we can create a nice visualization of our optimal solution:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/728/1*iL4PfhXTgG4MHbAYjuQ-Jw.png" /><figcaption>A visualization of our optimal solution. On the x-axis you see the number of attendants per day (which is displayed on the y-axis). The colours in each of the bars indicate the fraction of families on that day getting assigned a certain choice.</figcaption></figure><h3>Concluding words</h3><p>Bram and I were the 28th team to find this optimal solution. Given the fact that we had no experience in Linear Programming, we were very proud of our result in the end. We are now both awarded a silver medal, and I got promoted to being a “Competition Expert”.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1951386a6ba5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/helping-santa-plan-with-mixed-integer-programming-mip-1951386a6ba5">Helping Santa plan with Mixed Integer Programming (MIP)</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Creating a platform for AI competitions]]></title>
            <link>https://medium.com/data-science/creating-a-platform-for-ai-competitions-1184666f32e4?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/1184666f32e4</guid>
            <category><![CDATA[videogames]]></category>
            <category><![CDATA[bots]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Mon, 07 Jan 2019 11:00:01 GMT</pubDate>
            <atom:updated>2019-01-07T17:37:19.813Z</atom:updated>
            <content:encoded><![CDATA[<h3>Creating a platform for AI competitions in Python</h3><h4>Elaborating upon the most important aspects encountered during the development of a platform for an AI competition.</h4><p><a href="https://medium.com/@gillesvandewiele/creating-the-perfect-connect-four-ai-bot-c165115557b0">Last year</a> and <a href="https://medium.com/p/2d7662ffcbf6">this year</a>, I wrote a blog post about my solution for an AI competition which colleagues (<a href="https://telefoonboek.ugent.be/nl/people/802001314384">Elias</a>, <a href="https://telefoonboek.ugent.be/nl/people/802002430187">Pieter</a><a href="https://telefoonboek.ugent.be/nl/people/802001937309">, Ozan</a> and <a href="https://biblio.ugent.be/person/802001856372">Cedric</a>) and I created, specifically for first-year engineering students. In this competition, players can write their own agent that plays a game for them against agents of other players. To facilitate this competition, a platform was created that allowed the students to register themselves, upload their code and check the ranking of their agent on a leaderboard. The leaderboard is constantly updated based on results of games, simulated on a periodic basis. This blog post will discuss the creation of that platform, called Hexatron this year, in detail, and is organized as follows:</p><ol><li><a href="https://medium.com/p/1184666f32e4#c1c2">High-level overview and used technologies</a></li><li><a href="https://medium.com/p/1184666f32e4#5084">A detailed discussion of our simulator</a></li><li><a href="https://medium.com/p/1184666f32e4#6dcf">A discussion of our database technology and data scheme</a></li><li><a href="https://medium.com/p/1184666f32e4#0d83">Match-making and rating the skill of agents</a></li><li><a href="https://medium.com/p/1184666f32e4#5722">An overview of our front-end</a></li></ol><p><strong>Please note that this is only the second version of our platform. There is definitely room for improvement! Therefore, any kind of feedback is more than welcome and greatly appreciated.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/738/0*lc_3XafEVg_Ykfnw" /><figcaption>This year we even designed our own logo!</figcaption></figure><h3>High-level architecture and used technologies</h3><p>A high level overview of the different components in our system, and how they interact, can be found below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*o5YH9R7qkcuqMmbU9_Q1zw.png" /><figcaption>A (very) high-level overview of the architecture, consisting of three main modules: (i) a front-end for user registration, agent submission and display of our data, (ii) a SQL database with our data, and (iii) a runner that periodically samples two players from the database and simulates a game between them. Arrows depict the flow of data.</figcaption></figure><p><strong>We can distinguish 4 large components. The central component is our <em>back-end: </em>an SQL-based data store. Data concerning users and submitted agents is gathered through a <em>front-end</em> and stored in the <em>back-end</em>. Moreover, all the data is displayed through the <em>front-end</em> application. Periodically, a <em>Sampler</em> component extracts pair of users from the database in order to simulate a game between them, in docker containers, using the <em>Simulator</em> component. The pairs are formed in order to try and ensure competitive, exciting matches.</strong></p><h3>Agent compliance &amp; docker-based simulations</h3><p>As the games are simulated server-side, and because it is possible to cause harm to your hosting machine with python scripts (imagine shutil.rmtree(&#39;/&#39;) or exec(&#39;sudo smth&#39;)), some measures were taken in order to ensure that it would be impossible (or at least very hard) to submit an agent to our system and effectively cause harm to our server. This was realized through some <strong>initial checks when submitting code</strong> to our platform, and by trying to <strong>simulate games in a “sandbox” environment</strong>.</p><p>Each participant needs to implement a function that accepts a certain game state as input, and outputs a move that the agent wants to make. Each time he or she submits the newly written code our platform, we performed a few checks. First, we checked whether the file size of the uploaded file did not exceed more than a Megabyte. This to avoid users submitting solutions that would allocate too much space on our hard disk and to avoid hard-coding the optimal move for every possible game state. Second, we only allowed for NumPy and certain packages from the standard library to be used. Third, and finally, no top-level execution code was allowed (all code had to be wrapped in functions) and some constructs were forbidden including eval , exec , open , file , subprocess , dircache , and more. If all these checks succeeded, the latest submission of the corresponding user was updated to the new code, which would be used in the next simulation.</p><p>The simulations are performed using Docker containers. Each time a new agent is submitted to our platform, a docker container is created for that agent in which a flask server is running. This flask server has a post route, which accepts a game state and returns the agent his move. While Docker containers are not ideally suited as sandbox environments, it does make it much harder to break the system through submitted code.</p><h3>Back-end technology and data scheme</h3><p>As back-end technology, we used SQL. While it takes a little bit more of development effort than, for example, a simple MongoDB, it is often a lot more efficient. Our data scheme (which is probably way too complex) is depicted below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/321/1*n16xyZCJSiaklUBGd0m0Kw.png" /><figcaption>The data scheme used in our SQL store.</figcaption></figure><p>The central objects within our back-end are the <em>User</em>, <em>Submission</em> and <em>Game</em>. For each agent a <em>User</em> submits to our platform, a <em>Submission</em> object is created and added to the DB. Moreover, this newly added <em>Submission</em> is used to “overwrite” the user his <em>ActiveSubmission</em>. Our runner periodically samples pairs of <em>User</em> objects and runs a simulation between them. The results of that simulation are stored in a newly added <em>Game</em> object, resulting in the creation of a new <em>Rating</em> object as well that represents the users’ updated rank. While there is no real difference between the <em>ActiveSubmission </em>and <em>Submission </em>objects. We did make a distinction such that we could allow for functionality to switch between submitted agents.</p><h3>Match-making and skill rating</h3><p>Two important aspects of the competition is how a <em>ranking of an agent can be determined</em> as accurately as possible and how <em>competitive matches can be ensured</em> as much as possible. Again, existing algorithms and technologies were used to solve these.</p><p>In order to rank the agents, we first applied the <a href="https://en.wikipedia.org/wiki/TrueSkill">TrueSkill™</a> system, developed by Microsoft. TrueSkill is similar to the well-known <a href="https://en.wikipedia.org/wiki/Elo_rating_system">ELO</a> system (originating from chess), but comes with a few extra advantages such as being suited for games other than 1 versus 1 and naturally handling inactivity of players (whereas in the ELO system, these players would just remain around the same rank). While the mentioned advantages are not really relevant in our scenario (where the games are 1 versus 1 and inactivity does not occur because of the periodic sampling), the TrueSkill system is somewhat more recent and was therefore worth a shot. Unfortunately, we noticed that the TrueSkill rating changes way too slowly, making it hard for people that joined the competition later than others to achieve a high rank. Therefore, we refactored back to the ELO system half-way the competition.</p><p>To ensure competitive matches, we used an already existing algorithm called <a href="https://en.wikipedia.org/wiki/Blossom_algorithm"><strong>Blossom</strong></a><strong>,</strong> which finds the maximum matching in a graph. More formally: given a graph G = (V, E) the algorithm finds a matching <em>M</em> (which is a collection of edges) such that each vertex in <em>V</em> is incident with at most one edge in <em>M</em> and |<em>M</em>| (or sum of weights in our case) is maximized. The problem itself is very similar to the <strong>bipartite graph matching</strong> problem, which can be solved by applying the <a href="https://en.wikipedia.org/wiki/Hungarian_algorithm"><strong>Hungarian Algorithm</strong></a><strong> </strong>(which was the first thing we were looking into), but the latter creates a matching between two (different) sets of vertices (often representing people and jobs). As an example, assume we have four players within our system. One player <strong><em>(A)</em></strong> has a very strong agent, one player <strong><em>(B)</em></strong> has a very weak agent and the two other players <strong><em>(C, D)</em></strong> have average agents. Then we could represent our leaderboard using a weighted graph. This graph is fully connected, and each vertex corresponds to a player. The weight on each outgoing edge from a vertex corresponds to the match quality between those two players (the more competitive the players are to each other, the higher the quality):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/161/1*y4cyQZyKsD287a1wm6UI6A.png" /><figcaption>Representing our leaderboard of four players in a graph. The width of the edges depicts the match quality.</figcaption></figure><p>The Blossom algorithm would, in this case, return 2 edges such that the sum of their weights is maximized and such that each vertex in our graph is incident to exactly 1 of those edges. This is exactly what we want: each player is matched against another player and the total sum of match qualities is maximized. Of course, this is only possible when the number of vertices is even. In case of an odd number of players, 1 random player is uniformly sampled from all players and removed from the graph.</p><h3>Displaying everything in the front-end</h3><p>The front-end was mainly created using Flask. Each possible page from our platform corresponds to a route. When a user surfs to this route, the relevant objects are retrieved from the back-end and provided to a JINJA template which is then rendered. For the interactive parts of our application (such as the slider to filter games within a certain date range and the different visualizations), we used JavaScript and D3. Some screenshots of the application can be found below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*D39BzGdjEf-2wp5IctANWw.png" /><figcaption>Screenshot of the leaderboard page</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M3tH1lKH1HPmB-tqLjGkYQ.png" /><figcaption>Screenshot of the game history page</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*muvzuPbVInAJoW7mI0tXHw.png" /><figcaption>Creating a new account</figcaption></figure><h3>Concluding words</h3><p>So this is it. I’ve now given a quick overview of the aspects and components that required a significant part of our time during the development of our platform. I hope this can be helpful to some people out there that are currently trying to create something similar. As always: if anything is unclear, if there are things you would like me to further elaborate upon, or if you have suggestions or feedback, please do not hesitate to contact me! You can do this either through commenting on this post or by sending me a mail.</p><p>Perhaps next year, I can make another post about the changes we made in our third version of the yearly AI competition. See you then,</p><p>Gilles, <a href="https://telefoonboek.ugent.be/nl/people/802001314384">Elias</a>, <a href="https://telefoonboek.ugent.be/nl/people/802002430187">Pieter</a><a href="https://telefoonboek.ugent.be/nl/people/802001937309">, Ozan</a> and <a href="https://biblio.ugent.be/person/802001856372">Cedric</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1184666f32e4" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/creating-a-platform-for-ai-competitions-1184666f32e4">Creating a platform for AI competitions</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A simple, but strong AI bot for Tron/Lightriders on a hexagonal grid.]]></title>
            <link>https://medium.com/data-science/a-simple-but-strong-ai-bot-for-tron-lightriders-on-a-hexagonal-grid-2d7662ffcbf6?source=rss-3e8cbc53806e------2</link>
            <guid isPermaLink="false">https://medium.com/p/2d7662ffcbf6</guid>
            <category><![CDATA[towards-data-science]]></category>
            <category><![CDATA[pathfinding]]></category>
            <category><![CDATA[tron]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Gilles Vandewiele]]></dc:creator>
            <pubDate>Mon, 07 Jan 2019 10:59:36 GMT</pubDate>
            <atom:updated>2019-01-12T07:18:37.792Z</atom:updated>
            <content:encoded><![CDATA[<h3>A simple, but strong AI bot for Tron/Lightriders on a hexagonal grid</h3><h4>How a simple heuristic based on path-finding found a path towards the top-tier on the leaderboard.</h4><p>A new academic year, which means a new batch of bright students taking their first steps in their engineering career. <a href="https://medium.com/@gillesvandewiele/creating-the-perfect-connect-four-ai-bot-c165115557b0">As last year</a>, three of my fellow course assistants (<a href="https://telefoonboek.ugent.be/nl/people/802001314384">Elias</a>, <a href="https://telefoonboek.ugent.be/nl/people/802002430187">Pieter</a> and <a href="https://telefoonboek.ugent.be/nl/people/802001937309">Ozan</a>) and I created a <a href="https://hexatron.ilabt.imec.be/">platform for an AI bot competition</a>, to be hosted during the course of Informatics (in which they learn to program in Python), given by <a href="https://www.ugent.be/ea/idlab/en/members/bart-dhoedt.htm">prof. Dhoedt</a> at Ghent University. This year, we decided to host the game of Tron (sometimes called continuous snake or Lightriders), as shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*m0PMGpFeiP5ypQn-hHh-rQ.jpeg" /><figcaption>A more advanced implementation of the game Tron, called <a href="http://www.armagetronad.org/">Armagetron</a></figcaption></figure><p>Since both <a href="https://www.riddles.io/">Riddles.io</a> and <a href="https://www.codingame.com/">CodinGame</a> (which you should definitely check out if you are interested in AI bots!) host an AI competition for Tron as well, we decided to slightly adapt the game to be played on a hexagonal grid, instead of a square. This to avoid students just copy-pasting available solutions of those platforms. A screenshot of the game can be found below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/1*PKGt_P3O_cFcXVbQ8donhw.png" /><figcaption>A visualization of a match between two bots, which I lost. The darker colored tiles are starting positions.</figcaption></figure><p>As last year, I decided to compete in the competition myself, but did not find that much spare time. Hence, my solution wasn’t a very strong one. Nevertheless, I ended up pretty high on the leaderboard (5th spot), with a minimal code base and a simple heuristic, based on path finding.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/706/1*SX2YXAOdyi2jjZCohfVemA.png" /><figcaption>The top 10 of the final leaderboard. Again this year, we were amazed by the quantity and quality of many submitted agents by students. Notice how <a href="http://users.ugent.be/~jvdrhoof/">jvdhooft,</a> my partner in crime of last year, regretted his decision of not collaborating this year ;).</figcaption></figure><p>To discuss my solution, I will not need as much time/lines as last year, and therefore I decided to add some extra content. I split this blog post up in several sections:</p><h3>Table of content</h3><ol><li><a href="https://medium.com/p/2d7662ffcbf6#6e39">Game and competition rules</a></li><li><a href="https://medium.com/p/2d7662ffcbf6#3953">A detailed overview of my strong heuristic (with code)</a></li><li><a href="https://medium.com/p/2d7662ffcbf6#71db">A write-up by some of the top competitors</a></li><li><a href="https://medium.com/p/1184666f32e4">An overview of how the competition platform was made (separate post)</a></li></ol><h3>1. Game and competition rules</h3><h4>1.1 Game rules</h4><p>The rules of the game are rather straight-forward. Both players start at a random position (mirrored around the center of the map) and with a random orientation (there are 6 orientations in total). Each player must then decide if they want to rotate their snake (120° or 60° CW/CCW or 0°), before making a move forward (as depicted in the figure below). Each snake leaves behind an impenetrable trail. The first snake that crashes into a wall or a trail of himself or opponent, loses the game.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/355/1*aiBNpp5BQdup-3wethFZYA.png" /><figcaption>The five possible moves a player can make in each turn.</figcaption></figure><h4>1.2 Competition rules &amp; agent interface</h4><p>The submitted agents have to follow a predefined interface:</p><pre>def <strong>generate_move</strong>(board, positions, orientations):<br>  &quot;&quot;&quot;Generate a move.<br>     Args:<br>        board (np.array):    playing field<br>        positions (list):    list of positions `(x, y)`<br>        orientations (list): list of orientations (int in [0,5])</pre><pre>     Returns:<br>        move (int):          integer in [-2,2]<br>    &quot;&quot;&quot;<br>  return 0</pre><p>Moreover, each agent must comply to the following constraints:</p><ul><li>It contains no import statements, with the exception of: numpy, functools, itertools, collections, operator, heapq, math, random, time</li><li>The file size must not be larger than 1 Megabyte</li><li>The execution time of generate_move may not exceed 1 second</li></ul><p>After submitting your first agent to our platform, you will be matched up with another player every 30 minutes. After each match, rankings (<a href="https://en.wikipedia.org/wiki/TrueSkill">TrueSkill</a> or <a href="https://en.wikipedia.org/wiki/Elo_rating_system">ELO</a>) of both players are adjusted according to the match result, and these rankings are used for the leaderboard. For more information on the ranking systems, please refer to <a href="https://medium.com/p/1184666f32e4">my next post</a>.</p><h4>1.3 Regular competition and play-offs</h4><p>The competition lasted for about 1 month. We noticed that luck had a significant impact on your final rank (due to the matchmaking algorithm). To combat this, and to end up with an as objective ranking as possible, we took the top-competitors from the leaderboard after a certain amount of time (first-year students only). These competitors were chosen to compete in the “play-offs”, where each agent played all other agents four times. For each win, an agent was assigned three points, while a draw (of which there were many) resulted in both agents being awarded a single point.</p><h3>2. My strong heuristic based on pathfinding</h3><h4>2.1 Main loop</h4><p>Before implementing more complex techniques, such as reinforcement learning, genetic algorithms and alpha-beta pruning, it is always good practice to first implement an agent based on a heuristic. These can be used to test the strengths of your opponents, but more importantly the strength of later versions of your agent. Unfortunately, I did not manage to implement more complex techniques this year due to a lack of time and only uploaded my baseline agent, based on a heuristic (which turned out to be very strong). I will now discuss my implementation thoroughly.</p><p>The main reasoning behind my agent is rather simple: “always pick the move which results in a maximal difference between the number of tiles you can reach first, and the number of tiles your opponent can reach first.” Obviously, there will be many situations in which each possible move results in the same score (especially in the beginning of the game). We break ties by minimizing the number of remaining legal moves after making a certain move and by minimizing the distance towards the middle (if it still can be reached). The main game loop thus looks as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a563e3cfacd4821afb6fdf63f12ee7f9/href">https://medium.com/media/a563e3cfacd4821afb6fdf63f12ee7f9/href</a></iframe><h4>2.2 Getting all legal moves</h4><p>Now let’s break everything down, starting from (probably) the most simple part in the code: getting all legal moves (get_legal_moves). In this function, we iterate over each integer in the interval [-2, 2] which are the five possible moves. We map each integer to a tuple of offsets (get_steps) that correspond to our move and update our positions and orientations hypothetically (_update_pos_orient) according to these offsets. Then, we calculate whether we still reside in the hexagonal grid (_valid_position) and whether we did not crash into an already occupied cell (_no_crash):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0ab874cfd185efc4b9ed60542c7443ce/href">https://medium.com/media/0ab874cfd185efc4b9ed60542c7443ce/href</a></iframe><p>The code is rather straight-forward and probably does not need a lot of elaboration. To check whether we still reside in the hexagonal grid, we have to ensure that we do not get an IndexError by checking if our x and y coordinates do not go out of the bounds of our playing fields. Moreover, since the board representation is a square with some cells that are not reachable, we need to ensure that our agent does not move onto one of these cells. By inspecting the smaller (7x7) playing field depicted on the homepage we notice that the sum of x and y of the legal cells is bounded by 3 and 9.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*nsyyOzrDP1vN2Exz-oiLeA.png" /><figcaption>The x and y coordinates of the allowed tiles on a 7x7 field are bounded by 3 and 9.</figcaption></figure><p>This generalizes to all playing field sizes and we can thus say that:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/283/0*oRKukxPfU1LnfEU2.png" /></figure><p>with k the size of the playing field. Moreover, to check whether we are not moving on an already occupied cell, we can just take the sum along the final axis of our playing board (remember that the final axis of this board contains a bitmap for each player) and check whether the value at the coordinate we want to move to is equal to 0. Further, the order of the offsets in _get_steps is order specifically such that we can directly index them using our newly calculated orientation, which is equal to (orientation + action) % 6. Using this new orientation, we can get the corresponding offsets and add these to our current coordinates to calculate our new coordinate.</p><h4>2.3 Calculating the utility or score of a game state</h4><p>Now that we have a list of all the moves that will not result in us immediately losing, we can calculate a score for each of these moves, based on a heuristic. The heuristic we used is based on distances to each possible tile in the game field. We want to maximize the number of tiles we can reach in less moves than our opponent while minimizing the number of tiles he or she can reach first. A nice GIF, taken from the <a href="https://www.a1k0n.net/2010/03/04/google-ai-postmortem.html">winning solution’s write-up in the Google Tron AI Challenge</a> is displayed below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/120/0*xFwNwT-ELdaiLjYb.gif" /><figcaption>Maximizing the cells we (red) can reach first, while minimizing the cells our opponent (blue) can reach first results in a strong, but not optimal, heuristic.</figcaption></figure><p>To calculate the minimal distance from a certain coordinate to another cell, we can use the <a href="https://en.wikipedia.org/wiki/A*_search_algorithm">A* path-finding algorithm</a> or <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra</a>. But since we need to calculate a distance to all cells in our grid, we use a slightly adapted version. We keep track of a list of cells that still need to be visited (and the distances to each of these cells), called a frontier. For each cell in our frontier, we expand in all possible directions and add these new cells to our frontier (with a distance equal to our old distance + 1) if they have not yet been explored or if we discovered a path with a smaller amount of moves. Once we have calculated the distances to all cells for both players, we can easily calculate the number of tiles both players can reach first:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/60068e98be72f3f589cf7f8ae6bedfa5/href">https://medium.com/media/60068e98be72f3f589cf7f8ae6bedfa5/href</a></iframe><blockquote>And that’s it! It’s that simple. In summary, we retrieve a list of all possible legal moves we can make, we then iterate over these legal moves and calculate a score for each of them. The score is based on the number of tiles we can reach first from the new position after making that move and the number of tiles our opponent can reach first. There are a few extra details, such as subtracting a penalty term from the score if we are too close to our opponent to avoid head-to-head crashes and the handling in case of ties (which are broken based on the number of legal moves remaining to fill up the board and based on the distance to the middle, since that is important in the start of the game).</blockquote><h4>2.4 Possible improvements and other directions</h4><p>As mentioned, only a limited amount of time was spent this year on writing my agent. Therefore, many possible improvements are left open. The most important ones are listed here:</p><ul><li>An adaptation of the heuristic function could result in significant gains. According to the <a href="https://www.a1k0n.net/2010/03/04/google-ai-postmortem.html">write-up of the Google Tron AI Challenge</a> this resulted in the author winning the competition. In his blog post, a nice example game state is provided, where the heuristic function used for my agent would assign a negative score while we (again we are red) are actually on the winning hand:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/128/0*LNHnagg7TKJUwGDf.png" /><figcaption>According to our heuristic, red has much less tiles he can reach first than blue. But no matter what move blue makes now, red can easily win the game since it is impossible for blue to fill up all his tiles.</figcaption></figure><ul><li>Instead of calculating a score for each possible move, we could calculate a score for each possible sequence of moves, thus looking ahead more than 1 move. To solve this, we usually apply techniques such as <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">alpha-beta pruning</a>, but a few extra considerations will need to made since both players move simultaneously. One simple hack is to first retrieve all legal moves for your opponent, before iterating over all your legal moves (changing the game state) and then recursively call your opponent, passing along those moves. This ensures that both players can calculate their legal moves, using the same game state during the recursion.</li><li>Calculating the score for each possible move (or sequence of moves) using <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search">Monte Carlo simulations</a>, instead of using a heuristic function. Here, we would simulate a large number of games starting from a certain game state where each agent would make a random, but legal, move. The fraction of games we win from these simulations could be a good indication of the strength of a certain game state. Of course, it should be noted that the maximum time to make a move is only one second. I have not tested how many simulations one could make within that second.</li><li><a href="https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies">Evolving neural networks</a> to play the game for you, is a very generic strategy that requires no knowledge of the game itself. It would require quite a lot of work to write a framework for this (or configure an already existing one), but once it is written (or get the hang of the existing framework), it could easily be adapted for other games. I found a lot of examples for the single-player snake game (e.g. <a href="https://www.youtube.com/watch?v=edyRAnQO7N0">here</a> and <a href="https://www.youtube.com/watch?v=zIkBYwdkuTk">here</a>) but only a very small amount for continuous snake or tron (e.g. <a href="https://www.youtube.com/watch?v=JnBzhrEjlPo">here</a>).</li><li>Reading the write-ups of the other top competitors, and combining the most important insights from all to create a superbot.</li></ul><h3>3. Write-ups of the top competitors</h3><p>Below are write-ups of some of the solutions of students that were ranked higher than my agent in the end:</p><h4><strong>3.1. Michiel Platteau (#1 on final leaderboard, #2 in play-offs)</strong></h4><blockquote>The bot is a result of all its predecessors. Instead of writing new code all over again each time I made a lot of meta-functions. A lot of smaller functions can always be recycled to the next generation. These functions range from determining whether a move is legal, to calculating the number of available cells and distances to these cells. But combining all these functions can turn into something rather complex.</blockquote><blockquote>The code first calculates if the opponent is in the same field as him, if he isn’t he takes the most left moves with the maximal number of available cells (floodfill). If they are in the same field it’s all about having the best floodfill in the future. It starts by going to the center (6, 6). If the snakes start at the border he goes as wide as possible to try and trick the opponent, otherwise it takes the most central route to try to cut the field in equal halves. The center of the playing field is a very important position. I made a special function for this move. He looks which positions could give him advantage without giving the opponent advantage. If he doesn’t find a such position he moves towards the center, resulting in many possible options.</blockquote><blockquote>Once the bots are done fighting for center, I’ve defined a functions that simulates the field if my snake goes straight in every possible direction. It analyses if my bot can take advantage from there (bigger floodfill) and if distances to that spot is shorter. It analyses situations as ‘success’, ‘maybe draw’ or ‘success but longer distance’. For the moves I could make he also runs that function as if he was to opponent and doesn’t do moves that could result in advantage for the opponent. This can take a while, so it stops doing this after 0.7 seconds and it just assumes the opponent won’t have advantage. If no success moves are possible he tries to stay as close to center and the enemy as possible.</blockquote><h4>3.2. <a href="https://www.linkedin.com/in/kristiaanbogaerts">Kristiaan Bogaerts</a> (#2 on final leaderboard, #3 in play-offs)</h4><blockquote>At the beginning of every turn, the agent generates several <strong>variables</strong> based on the data it receives, some of them being 2D arrays with their length and width equal to the length and width of the playing board, others being single-element integers or Booleans. These <strong>variables</strong> serve as <strong>input</strong> for eventually deciding which hexagon adjacent to the agent is the most suitable to go to next, and consequently how the agent should rotate to reach that hexagon, which is the <strong>output</strong>.</blockquote><blockquote>The aforementioned <strong>variables</strong> generated by the agent include:</blockquote><blockquote>* a 2D array where each element that corresponds to a hexagon refers to the number of adjacent hexagons that are not occupied by one of both agents or their trails</blockquote><blockquote>* a 2D array where each element that corresponds to a hexagon refers to the shortest possible distance from that hexagon to the edge of the playing board (expressed in hexagons)</blockquote><blockquote>* a Boolean that indicates whether both agents can still reach each other</blockquote><blockquote>After calculating these <strong>variables</strong>, the agent assigns weights to the 2D arrays based on the values of the single-element variables. The 2D arrays are multiplied by their respective weights, and subsequently added together to construct a <strong>final 2D array</strong>. Each element in this <strong>final array</strong> that corresponds to a hexagon on the board has been assigned a value that is comparatively high if the agent estimates a comparatively high chance of winning the game by moving to that hexagon, and comparatively low if it estimates a comparatively low chance. Finally, the agent will check every hexagon around its position for the hexagon with the highest corresponding value in the <strong>final array</strong> and will output the rotation necessary to reach that hexagon.</blockquote><h4>3.3. Maxim De Clerq (<a href="http://www.linkedin.com/in/maxim-d-716472160">LinkedIn</a>, <a href="http://github.com/maximdeclercq">GitHub</a>) (#3 on final leaderboard, #1 in play-offs)</h4><blockquote>The final agent has two major versions, v8 and v10, where v10 has almost the exact same strategy as v8 except it’s much faster because it represents the board as a graph (which I’ll explain later).</blockquote><blockquote>Both agents have a large set of utility functions that allow to write code much faster because these can be copied between versions since their implementation stays the same (e.g. is position x playable? How many cells can the agent reach from position x? What is the distance between position x and y? What is the closest position in set s to position x?).</blockquote><blockquote>The rest of the code consists of algorithms to determine the best move. Most of these algorithms filter the moves that are playable and passes them on to another algorithm to break ties. The first algorithm determines if we must decide between two or more areas, and only passes the moves that lead to the larger area. Then the agent checks if we can reach the opponent, if that’s not possible, we can just fill the remaining area with a filler algorithm.</blockquote><blockquote>In all other cases it’s almost always optimal to go to the center of the board. If the agent is about to go to the center of the board, it first checks if the opponent can reach the center too. If he can, then the agent can possibly cut off the opponent by moving slightly to the left or slightly to the right, but only if the start positions were at the edge of the board and if cutting off results in a larger area than the area of the opponent.</blockquote><blockquote>If none of the above special cases occurred, the agent falls back on its general flooding algorithm, which makes the move with results in the most cells that it can reach first. If the opponent can reach a cell at the same time as the agent, it counts as half a cell.</blockquote><blockquote>If the flooding results in equal scores for several moves, it passes those moves to the multi ray casting algorithm, which is a rather old algorithm (v6) that casts rays from the position of both players and determines which move results in the largest area.</blockquote><blockquote>The biggest difference between v8 and v10 lies in the filler algorithm. While v8 only casts single rays from the players position to determine the largest possible area, v10 composes a graph from the grid. This is done by mapping every position in the grid to a number from 0 till 126. Because ray casting could still be useful, I had to define a direction for the nodes in the graph, so I defined a 127x5 grid where get_next_nodes()[node][direction % 6] would give me the node the agent would reach if it went in that direction. Then a rather complex convert function would turn the grid into an adjacency list. Instead of ray casting, the agent could now determine <a href="https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/">articulation points</a> in the graph. The agent can now fill the area by making the move that results in the least articulation points in the next two moves. This results in a perfect fill of any area.</blockquote><p><strong>IMPORTANT: </strong>Maxim published the code on <a href="http://github.com/maximdeclercq">his GitHub</a>. Be sure to check out the winning solution of the competition. You can even simulate games between mine and his agent!</p><h3>Concluding notes</h3><p>All code for the agent discussed within this blog post is available on <a href="https://github.com/GillesVandewiele/Hexatron-Bot">GitHub</a>. I did my best to clean and optimize the code as much as possible, but it is definitely not yet perfect. Therefore, submitting a pull request or opening issues is more than welcome!</p><blockquote>Moreover, as always, if anything in this blog post was unclear or requires further clarification, feel free to leave a comment, or contact me! If you have any cool suggestions for a game for next year, please feel free to leave a comment as well!</blockquote><p>Wow, you reached the end of this blog post! Kudos to you. See you next year for the third AI competition ;),<br>Gilles</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2d7662ffcbf6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/a-simple-but-strong-ai-bot-for-tron-lightriders-on-a-hexagonal-grid-2d7662ffcbf6">A simple, but strong AI bot for Tron/Lightriders on a hexagonal grid.</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>