Description

Recently, Money became interested in artificial intelligence and started learning about neural networks.

A neural network receives some input values, performs several calculations, and finally produces a score for each possible class. The class with the highest score is chosen as the prediction.

In this problem, Money uses a small neural network with the following structure:

input x
   |
   v
linear(x, W1, b1)
   |
   v
ReLU
   |
   v
hidden result h
   |
   v
linear(h, W2, b2)
   |
   v
output scores y
   |
   v
argmax(y)
   |
   v
predicted class

The first linear layer combines the input values using weights and biases. Then, the ReLU function replaces negative values with zero. The second linear layer produces one score for each class. Finally, argmax finds the class with the largest score.

Money has already written the main neural-network structure for you, but four important functions are still missing. Your task is to complete:

dot(a, b)
linear(x, W, b)
relu(x)
argmax(x)

All values in this problem are integers. You do not need to use NumPy, PyTorch, TensorFlow, softmax, or floating-point calculations.

Variables

• D: the number of values in each input vector.
• H: the number of neurons in the hidden layer.
• C: the number of output classes.
• x: one input vector given to the neural network.
• W1: the weights of the first layer. It transforms x into the hidden layer.
• b1: the biases of the first layer. One bias is added to each hidden neuron.
• h: the hidden-layer result after the first linear layer and ReLU.
• W2: the weights of the second layer. It transforms h into the output scores.
• b2: the biases of the second layer. One bias is added to each output class.
• y: the final output scores for all classes.
• Q: the number of input vectors to process.

Functions to Implement

1. dot(a, b)

Given two lists a and b of the same length, return their dot product.

a = [1, 2, 3]
b = [4, 5, 6]

The result is:

1*4 + 2*5 + 3*6 = 32

Therefore, dot(a, b) should return 32.

2. linear(x, W, b)

For every row W[i], calculate:

dot(W[i], x) + b[i]

Return all results as a list.

x = [2, 3]

W = [
    [1, 4],
    [2, -1]
]

b = [5, 2]

The result is:

[19, 3]

because:

1*2 + 4*3 + 5 = 19
2*2 + (-1)*3 + 2 = 3

3. relu(x)

For every value in x:

• If the value is negative, replace it with 0.
• Otherwise, keep it unchanged.

relu([-3, 5, 0, -7, 2])

returns:

[0, 5, 0, 0, 2]

4. argmax(x)

Return the index of the largest value in x. The first element has index 0.

argmax([7, 20, -3, 15])

returns:

1

If the largest value appears more than once, return the smallest index.

argmax([10, 20, 20, 5])

returns:

1

Neural Network Function

The following function has already been written for you:

def neural_network(x, W1, b1, W2, b2):
    h = linear(x, W1, b1)
    h = relu(h)

    y = linear(h, W2, b2)

    return argmax(y)

You do not need to modify this function.

Constraints

• 1 <= D, H, C <= 50
• 1 <= Q <= 1000
• Every weight, bias, and input value is between -100 and 100.
• All values are integers.

Starter Code

def dot(a, b):
    # TODO
    pass


def linear(x, W, b):
    # TODO
    pass


def relu(x):
    # TODO
    pass


def argmax(x):
    # TODO
    pass


def neural_network(x, W1, b1, W2, b2):
    h = linear(x, W1, b1)
    h = relu(h)

    y = linear(h, W2, b2)

    return argmax(y)


D, H, C = map(int, input().split())

W1 = []
for _ in range(H):
    W1.append(list(map(int, input().split())))

b1 = list(map(int, input().split()))

W2 = []
for _ in range(C):
    W2.append(list(map(int, input().split())))

b2 = list(map(int, input().split()))

Q = int(input())

for _ in range(Q):
    x = list(map(int, input().split()))
    print(neural_network(x, W1, b1, W2, b2))

Input

The first line contains three integers:

D H C

• D: the number of values in each input vector.
• H: the number of neurons in the hidden layer.
• C: the number of output classes.

The next H lines describe W1. Each line contains D integers. Therefore, W1 has H rows and D columns.

The next line contains H integers representing b1.

The next C lines describe W2. Each line contains H integers. Therefore, W2 has C rows and H columns.

The next line contains C integers representing b2.

The next line contains one integer:

Q

where Q is the number of input vectors to process.

The following Q lines each contain D integers, representing one input vector x.

In short, the input is given in the following order:

D H C
H lines of W1
1 line of b1
C lines of W2
1 line of b2
Q
Q input vectors

Output

For each input vector x, print the predicted class returned by:

neural_network(x, W1, b1, W2, b2)

Print one answer per line.

Each answer is an integer from 0 to C - 1, representing the index of the class with the largest output score.

If more than one class has the same maximum score, the class with the smallest index is chosen.

Sample Input  Download

Sample Output  Download

Tags

Discuss