Hide

# Problem CPerceptron Learning Algorithm

Implement the Perceptron Learning Algorithm (PLA) in to find a hypothesis in $d$ dimensions:

$h(x) = \textrm{sign}(w_0 + w_1 x_1 + w_2 x_2 + \ldots + w_ d x_ d).$

In other words, given a set of example pairs $(x, y)$, where $x \in \mathbb {R}^ d$ and $y \in \{ -1,+1\}$, use the PLA to identify a set of good weights $w_0$ through $w_ d$ for classifying the given examples.

## Input

Input for your program is a training set of $n$ examples in $d$ dimensions.

The first line contains two integers $1 \le n \le 10\, 000$ and $1 \le d \le 10$. Following are $n$ lines, each containing $d$ real numbers and one integer. The first $d$ numbers are for values $x_1$ through $x_ d$, and the last is for the corresponding $y$ value, which is either $-1$ or $1$. Each real value has at most $5$ digits past the decimal point and is in the range $[-2 \cdot 10^9, 2 \cdot 10^9]$.

## Output

Implement the Perceptron Learning Algorithm (or the Pocket algorithm) to create a perceptron model that fits the data as well as possible. Output $d+1$ real values corresponding to the coefficients $w_0$ to $w_ d$ in the definition of $h(x)$ above.

Note that the sample output shown is actually the test data on which a model would be evaluated (see below). It is in the same format as the input. A reasonable output for the given sample input might be:

-722.0 8.0 13.0


which would give a score of $80.0$ on the test data, according to the metric below.

## Scoring

Each time your program runs, it will process a different training set. The output of your program will be used to construct a perceptron to evaluate on another set of data, called the testing set. The testing set comes from a distribution similar to the training set, but is not known to your program.

Assume that the test data has $m$ examples $\{ (x(1),y(1)), \ldots , (x(m),y(m))\}$. The score your model receives for each test case is based on the accuracy on these $m$ examples (times $100$):

$\frac{100}{m} \cdot \sum _{i=1}^ m [h(x(i)) = y(i)]$

where $[\alpha ]$ is the indicator function (which is $1$ if the condition inside is true and $0$ otherwise).

The overall score for your submission is the average of the scores it receives for all hidden test cases. The sample data is excluded from this average.

Sample Input 1 Sample Output 1
6 2
77 66 1
86 14 1
50 21 -1
42 82 1
28 78 1
22 32 -1

10 2
23 47 -1
26 2 -1
96 78 1
1 65 -1
64 40 1
13 68 1
24 5 -1
69 32 1
21 19 -1
65 88 1