Implement Perceptron

Question

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 code-golf. 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]
    }
]

Answer 1

JavaScript (ES6), 102 bytes

-1 by @l4m2

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))?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
      )) >= t               //     end of map(); 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

Answer 2

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

Answer 3

Wolfram Language (Mathematica), 45 bytes

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

Try it online!

Answer 4

Charcoal, 41 39 bytes

≔⁺ＡＥＡ±ιθ≔§θ⁰ηＷΦ講ΣＥκ×μ§ην⁰ＵＭη⁺ꧧι⁰λＩη

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

≔⁺ＡＥＡ±ιθ

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.)

ＷΦ講ΣＥκ×μ§ην⁰

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

ＵＭη⁺ꧧι⁰λ

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

Ｉη

Output the final vector.

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

≔⁺Ａ±Ａθ≔§θ⁰ηＷΦ講Σ×κη⁰ＵＭη⁺ꧧι⁰λＩη

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.