<?xml version="1.0" encoding="UTF-8" ?>
<?xml-stylesheet type="text/xsl" href="https://community.arm.com/utility/feedstylesheets/rss.xsl" media="screen"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/"><channel><title>John Smith's Groups Activities</title><link>https://community.arm.com/members/john-smith</link><description>Recent activity for people in John Smith's group</description><dc:language>en-US</dc:language><generator>Telligent Community 10</generator><item><title>Ask A Question I</title><link>https://community.arm.com/achievements/460ac7df-7ccc-4c42-a204-9e05eef3be09</link><pubDate>Mon, 09 Nov 2020 02:24:46 GMT</pubDate><guid isPermaLink="false">dd9e70c8-6d3c-4c71-b136-2456382a7b5c:c8d31f1f-3672-4521-bdf2-bbdd4ccfc284</guid><dc:creator /><description>Ask a question in a forum.</description></item><item><title>Top-k scoring across multiple dimensions</title><link>https://community.arm.com/developer/tools-software/oss-platforms/f/machine-learning-forum/48011/top-k-scoring-across-multiple-dimensions</link><pubDate>Mon, 09 Nov 2020 10:49:03 GMT</pubDate><guid isPermaLink="false">dd9e70c8-6d3c-4c71-b136-2456382a7b5c:564feb05-5c71-406a-ad6e-bc215a315572</guid><dc:creator>John Smith</dc:creator><description>&lt;p&gt;In e.g. Natural Language Processing in &lt;a href="https://intellipaat.com/blog/what-is-machine-learning/" rel="noopener noreferrer" target="_blank"&gt;Machine Learning&lt;/a&gt;, a beam-search is often used to predict the next objects to add on to a sequence and rank them. A key part of the beam-search is the top-&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;score metric, which is effective: Given a list of choices of length&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;of probability scores, return the top&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;scoring items of&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;. This is as simple as sorting a list and then taking the top values.&lt;/p&gt;
&lt;p&gt;Referring to a visual example&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;a href="https://www.researchgate.net/figure/A-partially-completed-beam-search-procedure-with-a-beam-width-of-5-for-an-example-input_fig2_317377611" rel="nofollow"&gt;https://www.researchgate.net/figure/A-partially-completed-beam-search-procedure-with-a-beam-width-of-5-for-an-example-input_fig2_317377611&lt;/a&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;in a beam-search (in the above case,&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;=5, and a &amp;lsquo;top&amp;rsquo; score is a minimal value), at each iteration, each node selects the top&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;items from the list of choices&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;, resulting in&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;2&lt;/sup&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;total potential paths. From these paths, the top&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;overall are filtered, which form the nodes for the next iteration. In the previous example, you can see only the filtered nodes at each time-step.&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;a href="https://d2l.ai/_images/beam-search.svg" rel="nofollow"&gt;https://d2l.ai/_images/beam-search.svg&lt;/a&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;expands the case of&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;=2,&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;=5 comprehensively.&lt;/p&gt;
&lt;p&gt;Imagine, instead of optimizing one choice from&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;for each branch/node, you had to choose multiple values: When exploring from a node, you have a set of choices of dimension (&lt;em&gt;N&lt;/em&gt;,&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;) from which you want to select&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;values, one from each column&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;. Then, to find the highest-scoring sets of choices, you need to consider combinations of the values in these columns. For example: For a matrix of choices&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;=5,&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;=4:&lt;/p&gt;
&lt;p&gt;&lt;pre class="ui-code" data-mode="html"&gt;+---+--------+--------+--------+--------+
| N |   q0   |   q1   |   q2   |   q3   |
+---+--------+--------+--------+--------+
| 0 | 0.9763 | 0.0791 | 0.1530 | 0.5565 |
| 1 | 0.1560 | 0.1014 | 0.6932 | 0.7551 |
| 2 | 0.8142 | 0.9494 | 0.4582 | 0.4411 |
| 3 | 0.3807 | 0.2403 | 0.6897 | 0.7356 |
| 4 | 0.0156 | 0.9419 | 0.9568 | 0.2266 |
+---+--------+--------+--------+--------+
&lt;/pre&gt;&lt;/p&gt;
&lt;p&gt;If&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;=5, this top-&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;function should return the following:&lt;/p&gt;
&lt;ol&gt;
&lt;li&gt;3.6376 = q&lt;sub&gt;0&lt;/sub&gt;[0] + q&lt;sub&gt;1&lt;/sub&gt;[2] + q&lt;sub&gt;2&lt;/sub&gt;[4] + q&lt;sub&gt;3&lt;/sub&gt;[1]&lt;/li&gt;
&lt;li&gt;3.6301 = q&lt;sub&gt;0&lt;/sub&gt;[0] + q&lt;sub&gt;1&lt;/sub&gt;[4] + q&lt;sub&gt;2&lt;/sub&gt;[4] + q&lt;sub&gt;3&lt;/sub&gt;[1]&lt;/li&gt;
&lt;li&gt;3.6181 = q&lt;sub&gt;0&lt;/sub&gt;[0] + q&lt;sub&gt;1&lt;/sub&gt;[2] + q&lt;sub&gt;2&lt;/sub&gt;[4] + q&lt;sub&gt;3&lt;/sub&gt;[3]&lt;/li&gt;
&lt;li&gt;3.6106 = q&lt;sub&gt;0&lt;/sub&gt;[0] + q&lt;sub&gt;1&lt;/sub&gt;[4] + q&lt;sub&gt;2&lt;/sub&gt;[4] + q&lt;sub&gt;3&lt;/sub&gt;[3]&lt;/li&gt;
&lt;li&gt;3.4755 = q&lt;sub&gt;0&lt;/sub&gt;[2] + q&lt;sub&gt;1&lt;/sub&gt;[2] + q&lt;sub&gt;2&lt;/sub&gt;[4] + q&lt;sub&gt;3&lt;/sub&gt;[1]&lt;/li&gt;
&lt;/ol&gt;
&lt;p&gt;which are the largest possible sums, using one value from each column.&lt;/p&gt;
&lt;p&gt;Solving this for arbitrary&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;and&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;, the naive approach would be to calculate all&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;N&lt;/em&gt;&lt;sup&gt;&lt;em&gt;q&lt;/em&gt;&lt;/sup&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;sums, sort them, then take the top&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;results. The first step of optimization would be to sort each column, then only calculate the combinations of sums from the top&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;values in each column, reducing the complexity to&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;&lt;em&gt;q&lt;/em&gt;&lt;/sup&gt;.&lt;/p&gt;
&lt;p&gt;However, given this function to find top scores must be called&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;times every time-step of the beam-search, every possible speedup is vital if one wishes to scale to high&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;or high&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;. The best solution I&amp;rsquo;ve come up with (condensed to a minimum example, assuming&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;strong&gt;matrix&lt;/strong&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;is a NumPy array of shape (&lt;em&gt;N&lt;/em&gt;,&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;), and taking&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;to be 4):&lt;/p&gt;
&lt;p&gt;&lt;pre class="ui-code" data-mode="html"&gt;import numpy as np
from itertools import combinations


class Beamsearch():
    def __init__(self, klen, q=4):
        self.klen = klen
        self.combis = []
        for lens in range(klen):
            self.combis.extend(list(self.partition(lens, q)))
        self.width = q
        self.wdth = list(range(q))

    def partition(self, N, size):
        n = N + size - 1
        for splits in combinations(range(n), size - 1):
            yield [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]

    def getkmaxscores(self, matrix):
        matrix_argsort = np.argsort(-matrix, axis=0)
        sums = []
        for comb in self.combis:
            midxs = matrix_argsort[[comb], [self.wdth]]
            midxslist = midxs.tolist()
            msum = (sum(matrix[midxs, [self.wdth]]),
                    midxslist)
            sums.append(msum)
        sums.sort(reverse=True)
        return sums[:self.klen]&lt;/pre&gt;&lt;/p&gt;
&lt;p&gt;This method creates partitions of integers&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;p&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;into a given width&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;for integers&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;code&gt;0 &amp;le; p &amp;le; k&lt;/code&gt;, e.g. for&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;=4:&lt;/p&gt;
&lt;p&gt;&lt;pre class="ui-code" data-mode="text"&gt;p0: [0, 0, 0, 0]
p1: [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]
p2: [0, 0, 0, 2], [0, 0, 1, 1], [0, 0, 2, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 2, 0, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0], [2, 0, 0, 0]
&lt;/pre&gt;&lt;/p&gt;
&lt;p&gt;etc.&lt;/p&gt;
&lt;p&gt;These are then used to index the are sorted input matrix, to select each combination for summation. The length of&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;p&lt;/em&gt;&lt;sub&gt;i&lt;/sub&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;in the case&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;q&lt;/em&gt;=4 follows the triangular pyramidal sequence (&lt;a href="https://oeis.org/A000292" rel="nofollow"&gt;https://oeis.org/A000292&lt;/a&gt;): This reduces the search space to the sum of all p&lt;sub&gt;0...k&lt;/sub&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;which is the Binomial coefficient&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;code&gt;(k,4) = k(k-1)(k-2)(k-3)/24&lt;/code&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;(&lt;a href="https://oeis.org/A000332" rel="nofollow"&gt;https://oeis.org/A000332&lt;/a&gt;). This is a vast improvement over the&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;4&lt;/sup&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;solution for small&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;(for&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;span&gt;&amp;nbsp;&lt;/span&gt;&amp;lt; 30, this is less than&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;3&lt;/sup&gt;), but still grows on the order of&lt;span&gt;&amp;nbsp;&lt;/span&gt;&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;4&lt;/sup&gt;. Does there exist a solution to the arbitrary case with complexity &amp;lt;O(&lt;em&gt;k&lt;/em&gt;&lt;sup&gt;&lt;em&gt;q&lt;/em&gt;&lt;/sup&gt;)?&lt;/p&gt;&lt;div style="clear:both;"&gt;&lt;/div&gt;</description></item></channel></rss>