10
\$\begingroup\$

There was a previous perceptron question but it was closed. Also it required a lot of extra stuff that's not normally part of the perception algorithm like I know it. This question will be much simpler

The Perceptron is a extremely basic classification algorithm. While it still has some limited use it's been mostly overtaken by gradient descent based algorithms that can match much more complex functions. Still its fun and easy to implement, and is the foundation for many more complex algorithms.

The dot product is defined as follows:

$$(A_0, A_1, \dots, A_n) \cdot (B_0, B_1, \ldots, B_n) = A_0 B_0 + A_1 B_1 + \ldots + A_n B_n$$

Algorithm Description

Percepron can classify vectors into 2 categories, simply by taking the dot product with some vector. If this is positive, you are in category A, if negative, then not.

The algorithm to compute this vector works as follow:

set the initial vector to <0, 0, ..., 0>

while not every data point is classified correctly:
    let p be the first incorrectly classified point
    if the dot product is positive or zero but it should be negative:
        add p to the vector
    if the dot product is negative or zero but it should be positive:
        subtract p from the vector

Sample Implementation

Among the many weaknesses of this algorithm is that it runs forever if no solution exists, that it can only classify categories separated by a straight plane, and that that plane must pass through the origin.

You do not need to follow this exact algorithm as long as you can guarantee a correct vector in all the cases this algorithm would.

The task

Take as input a list of positive tuples and a list of negative tuples. All tuples will all be the same length, and can contain any real number representable by a 32 bit float. Then output a vector that perfectly classifies them.

This is . Shortest answer in each language wins.

You may also take input as a single list of ((x0, ..., xn), category) tuples. You may take the length of the tuples as a extra input if desired.

You may assume a solution exists for the input given.

The tuples in the input will always have 1 as their last value, representing bias.

Test Cases

Note: There are many vectors that can classify the data, any of them would be a valid result. Your code may still be correct if it produces very different values from this.

[
    {
        "positive": [[1,0, 1]],
        "negative": [[0,1,1]],
        "result": [1,-1,0]
    },
    {
        "positive": [[12.12958530911699, 71.71547437602891, 17.615042787292396, 1.0], [22.894324259518754, 7.747740085241489, -16.379692578583914, 1.0], [-77.19508767650036, 26.391457800328325, -34.128081828012256, 1.0], [96.46713849700853, 8.223882871718914, 95.59810235088628, 1.0], [95.47166665625838, 36.07081574287895, 20.660512993212635, 1.0]],
        "negative": [[-41.92974660410673, -42.941790456679854, 21.407959882725905, 1.0], [-99.40397441836177, 26.174868779681844, 56.51788064358769, 1.0], [34.482060088467364, -96.36102804944655, 1.5810491199434153, 1.0], [-43.06995918058733, -65.8456447109237, -99.04122951157478, 1.0], [7.7462310407688335, -10.894130800401939, 77.86204331190197, 1.0], [44.47180923569721, -93.53543659179937, 6.715910740415197, 1.0], [71.16273132699712, -80.16856861976358, 48.05726245445331, 1.0]],
        "result": [78.64936114023355, 237.2180619264857, -42.5708443640236, 10.0]
    },
    {
        "positive": [[19.891204296811196, 10.95935510782877, 25.985095341720097, -39.87626202198886, 13.054847014298801, -0.8134570474536389, -54.24129976411458, 1], [-16.576268085926657, 4.5002152868197385, 6.698984554370156, -49.780067496976976, 3.9392362908185703, -11.457246915347255, -3.84485029930714, 1], [-6.424223219895211, -67.86203596702003, 0.6670934629448197, -67.56926034741468, -34.71326779844648, -19.40781793399796, -38.93217338522913, 1], [-55.06122442753092, -46.49216596542017, -28.522294222446035, -30.89448675440849, 25.85546157303159, -28.753484757197114, -67.37074950075419, 1], [12.753734640663126, -42.688681313433065, -37.073894323478854, -22.678023584770216, -12.23724620287598, 4.467063264393019, -28.749388172615724, 1], [-25.894264060028036, -4.384289071814308, 25.545930397049247, -53.005653882689884, -17.7501576060518, -19.66585588898353, -33.29502103119091, 1], [-32.104636572417846, -61.44888846917201, -41.89407929533455, 20.32097494020971, 8.703788581939762, 12.493571659393822, -35.255247777162495, 1], [24.15536843650885, -25.610207061176325, 16.08185788882571, -34.478497500787185, -18.915615320612233, 24.782283056323323, -24.770226555932894, 1], [6.765979248514711, -1.6248990886835486, 19.091220818794667, 14.715692506417057, 7.953257187955259, 12.722665623234263, 14.914783085366352, 1]],
        "negative": [[-2.7270414497182855, 8.676310678740919, -72.98709301742022, -7.70910010724549, 10.477333664984855, -17.506198964389014, 18.233248667960424, 1], [-43.3010158973477, -20.807005424922295, -77.5083019019948, 16.126838313178908, -40.490353240152864, -11.81562605632648, -8.902497984641357, 1], [-31.71159835398403, -14.73301578999785, 13.902967116929815, -21.834371921202447, -40.86878402777407, 6.742152812766307, -16.213431636063206, 1], [-66.57071699396832, -2.6930106603672783, 24.856421108284607, 26.02555433076685, -45.195502153813656, -60.583102046347044, 18.622821621702442, 1], [-47.07567023723187, 8.668277396085415, -55.64099369519978, -24.3651014072761, -77.50500543887348, -29.67008512028478, -27.6004244984169, 1], [16.02465948636585, -64.28947887797132, -18.663992818184852, 11.001922130635734, -65.96111461946506, -70.07973218635979, -41.525576739268594, 1], [-33.6451045267202, -8.496296235717935, -20.129571219612984, 9.152732883489037, 10.242775447179753, -61.865587395289765, -32.78507965995476, 1], [-59.32306321222039, 12.522731642519034, 22.026994802405454, -18.062615366497297, -8.713470639955815, -44.04186584475624, 27.84951438666559, 1], [15.30669132488326, 4.865567302204951, -2.782248675090557, 24.252984759612147, -31.883249650258065, 0.5697927616565579, 22.431436239098076, 1], [1.0357436812954433, -32.44164907799862, 13.942522314820707, 16.30751529733827, -12.905194523861582, -22.446463524560656, 12.651474924205772, 1], [-56.03563699153419, 12.024854226295957, -39.90028407341309, 26.9268535257967, 23.808505964904285, 0.34968582027003947, -29.362006601750707, 1], [-85.14402438073334, -15.501824729148709, -63.38128746811267, -42.15734961052637, -4.1615796887736565, -7.25189532732314, -27.223088213381402, 1], [2.7529807581849184, -23.668062096200217, -9.028343561579462, 2.5495275958544283, 15.88901518194605, -59.28742737700396, 25.402434735936126, 1], [-49.514159298902705, -24.01610873489301, 19.949647054069544, -41.1158129509881, -53.808681913915706, -11.175092994514387, 16.753648710377945, 1], [13.052884356788013, -29.298799492103925, -11.675938518634197, -11.229831992030299, -82.661335125941, 0.4488670991709114, 15.5168860373427, 1], [-10.923814330565236, -44.964063927868544, -38.9909686186201, 15.763631832856007, -44.00734436715622, -54.69686019599016, -52.81999206838163, 1], [-43.815947420234714, 19.90446963235277, 4.773988726751696, -47.12560089860667, 13.028054180292472, -39.81105100874389, 16.639915018971934, 1], [-60.88215048423795, 18.63815015768826, 27.157195120177462, -31.93335885907136, -6.562377024790365, 20.3179674395969, 9.210423673803817, 1], [-20.199358866077134, -50.594347683405196, -65.49273675929138, 19.37323156150201, -13.877303200574588, 19.536120330891066, -17.908737459942998, 1], [-11.03148069515855, 18.400073052625856, -65.34212863735566, -5.32988003172234, 0.7010084382675785, 26.36787095325562, 22.718825279142763, 1], [-30.028696420764177, -20.038640467728513, -47.66006964061526, 1.669739637216125, 3.3366149257696947, -20.495524621115493, 11.79886970131642, 1]],
        "result": [53.402165827630355, -96.34048665666451, 46.75018310196545, -58.648563298215464, 167.65173848467344, 54.84963473487821, -66.47771531555354, 6.0]
    }
]
\$\endgroup\$
2
  • \$\begingroup\$ May we take input as a single list of vectors, where the category B vectors are negated? (e.g. the first test case would be [[1,0,1],[0,-1,-1]]) \$\endgroup\$
    – tjjfvi
    Nov 17 at 16:53
  • \$\begingroup\$ @tjjfvi No, that would trivialize the challenge. You can negate category B yourself though, but include that code in your byte count \$\endgroup\$
    – mousetail
    Nov 17 at 16:56

4 Answers 4

5
\$\begingroup\$

JavaScript (ES6), 103 bytes

Expects [ positive, negative ].

A=>(g=V=>A.some((a,j)=>a.some(v=>(q=v.map((c,i)=>(x=V[c*=1-2*j,i]||0,t+=c*x,c+x),t=0),t<=0)))?g(q):V)``

Try it online!

Commented

A => (                      // A = [ positive, negative ]
  g = V =>                  // g is a recursive function taking the vector V
  A.some((a, j) =>          // for each array a[] at position j in A[]:
    a.some(v => (           //   for each vector v[] in a[]:
      q = v.map((c, i) =>   //     for each value c at position i in v[]:
        (                   //
          x = V[            //       set x to V[i], or 0 by default
            c *= 1 - 2 * j, //       multiply c by the expected sign
            i               //       (+1 if j = 0, -1 if j = 1)
          ] || 0,           //
          t += c * x,       //       add c * x to t
          c + x             //       set q[i] = c + x
        ),                  //
        t = 0               //       start with t = 0
      ),                    //     end of map()
      t <= 0                //     trigger both some() if t <= 0
    ))                      //   end of inner some()
  )                         // end of outer some()
  ?                         // if truthy:
    g(q)                    //   recursive call with V = q
  :                         // else:
    V                       //   stop the recursion and return V
)``                         // initial call to g with a dummy vector
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 38 35 34 bytes

¬[©¹.Δ®*O(d}DÄi².Δ®*Od}DÄi®qës\-ë+

Naive port of the example implementation. Takes two separated lists of lists as inputs, the first being the positive list and the second the negative.

Try it online or verify all test cases.

Explanation:

н                # Get the first tuple of the first (implicit) positive input-list
[                # Start an infinite loop:
 ©               #  Store the current vector-list in variable `®` (without popping)
  ¹              #  Push the first positive input-list
   .Δ            #  Pop and find the first inner list which is truthy for:
                 #  (or -1 if none are truthy)
     ®           #   Push the vector-list
      *          #   Multiply the values in the two lists at the same positions
       O         #   Sum this list together
        (        #   Negate this sum
         d       #   And check if this -sum is non-negative (>=0)
                 #   (the `(d` is basically a sum<=0 check)
    }D           #  Duplicate the result of the find-first
      Äi         #  If it's -1 (thus none were found):
        ².Δ®*Od} #   Do another find-first on the second negative input-list,
                 #   but this time with sum>=0 check instead of sum<=0
     DÄi         #   Again similar; if it's -1 (thus none were found):
        ®        #    Push the vector-list
         q       #    And stop the program
                 #    (after which this vector-list is output implicitly as result)
       ë         #   Else (a result is found for the negative list):
        s\       #    Discard the positive result from the stack
          -      #    And subtract the values of the negative result from the vector-
                 #    list at the same positions
       ë         #  Else (a result is found for the positive list):
        +        #   Add the values of the positive result and the vector-list together
                 #   at the same positions
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 45 bytes

0~LinearOptimization~{a=#~Join~-#2,-1^Tr/@a}&

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 41 39 bytes

≔⁺AEA±ιθ≔§θ⁰ηWΦ講ΣEκ×μ§ην⁰UMη⁺ꧧι⁰λIη

Try it online! Link is to verbose version of code. Explanation:

≔⁺AEA±ιθ

Concatenate the two lists of input vectors but negate the second one.

≔§θ⁰η

Edit: Saved 2 bytes by stealing @KevinCruijssen's trick of using the first input vector as the initial output vector. (This works because a vector of all zeros incorrectly classifies all of the input vectors so the first step is to add the first input vector to the vector of all zeros.)

WΦ講ΣEκ×μ§ην⁰

While the list of input vectors that do not have positive dot products with the output vector is not empty...

UMη⁺ꧧι⁰λ

... add the first such vector to the output vector.

Iη

Output the final vector.

34 33 bytes using the newer version of Charcoal on ATO:

≔⁺A±Aθ≔§θ⁰ηWΦ講Σ×κη⁰UMη⁺ꧧι⁰λIη

Attempt This Online! Link is to verbose version of code. Explanation: Saved 2 bytes because Negate fully vectorises. Saved 1 byte because Times fully vectorises. Saved 4 bytes because Times can pairwise multiply vectors.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The algorithm will actually output a correct value regardless of the initial vector chosen, though not necessarily the same one. \$\endgroup\$
    – mousetail
    Nov 18 at 10:22
  • \$\begingroup\$ @mousetail So could I in fact add any incorrectly classified vector, not just the first? That would save me two bytes. \$\endgroup\$
    – Neil
    Nov 18 at 20:53
  • \$\begingroup\$ Yes you could . \$\endgroup\$
    – mousetail
    Nov 19 at 6:56
  • \$\begingroup\$ @mousetail So for the second test case, any of the following could be valid answers? [43.85867624623019, 250.61661326826788, -31.104689278496252, 0], [20.80703668675153, 159.59767032336953, 1.6793562995596432, -2], [171.55792950793102, 184.46682969557543, -4.189877336509852, -2], [92.63819643859534, 137.7447271542578, -27.972221746522962, 1]? \$\endgroup\$
    – Neil
    Nov 20 at 13:31
  • \$\begingroup\$ If they perfectly classify the data, yes. For example in the first test case (any positive number, any negative number, something close to 0) would be valid \$\endgroup\$
    – mousetail
    Nov 20 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.