<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step1:  Your task starts here
First, let's write a function that predicts class for given X.
Since the problem above isn't linearly separable, we add quadratic features to the classifier. This transformation is implemented in the expand function.
Don't forget to expand X inside classify and other functions
Sample classification should not be much harder than computation of sign of dot product.
Step4:  The loss you should try to minimize is the Hinge Loss
Step5:  Training
Find an optimal learning rate for gradient descent for given batch size. 
You can see the example of correct output below this cell before you run it.
Don't change the batch size!
Step6:  Implement gradient descent with momentum and test it's performance for different learning rate and momentum values.
Step7:  Same task but for Nesterov's accelerated gradient
Step8:  Same task but for AdaGrad
Step9:  Same task but for AdaDelta
Step10:  Same task for Adam algorithm. You can start with beta = 0.9 and mu = 0.999
<ASSISTANT_TASK:>
Python Code:
def expand(X):
    X_ = tf.zeros((X.shape[0], 6))
    X0 = tf.transpose(tf.gather(tf.transpose(X), [0]))
    X1 = tf.transpose(tf.gather(tf.transpose(X), [1]))
    X_ = tf.concat([X, X ** 2, X0 * X1, tf.ones(shape=(X.shape[0], 1))], axis=1)
    return X_
def classify(X, w):
    
    Given feature matrix X [n_samples,2] and weight vector w [6],
    return an array of +1 or -1 predictions
    
    pass
Explanation: Your task starts here
First, let's write a function that predicts class for given X.
Since the problem above isn't linearly separable, we add quadratic features to the classifier. This transformation is implemented in the expand function.
Don't forget to expand X inside classify and other functions
Sample classification should not be much harder than computation of sign of dot product.
End of explanation
def compute_loss(X, y, w):
    
    Given feature matrix X [n_samples,2], target vector [n_samples] of +1/-1,
    and weight vector w [6], compute scalar loss function using formula above.
    
    pass
    
def compute_grad(X, y, w):
    
    Given feature matrix X [n_samples,2], target vector [n_samples] of +1/-1,
    and weight vector w [6], compute vector [6] of derivatives of L over each weights.
    
    pass
Explanation: The loss you should try to minimize is the Hinge Loss:
$$ L =  {1 \over N} \sum_{i=1}^N max(0,1-y_i \cdot  w^T x_i) $$
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Training
Find an optimal learning rate for gradient descent for given batch size. 
You can see the example of correct output below this cell before you run it.
Don't change the batch size!
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
mu    = 0 # momentum
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Implement gradient descent with momentum and test it's performance for different learning rate and momentum values.
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
mu    = 0 # momentum
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Same task but for Nesterov's accelerated gradient:
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
mu    = 0 # momentum
eps = 1e-8  # A small constant for numerical stability
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Same task but for AdaGrad:
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
beta = 0
mu    = 0 # momentum
eps = 1e-8  # A small constant for numerical stability
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Same task but for AdaDelta:
End of explanation
w = np.array([1,0,0,0,0,0], dtype=tf.float32)
alpha = 0 # learning rate
beta = 0  # (beta1 coefficient in original paper) exponential decay rate for the 1st moment estimates
mu   = 0  # (beta2 coefficient in original paper) exponential decay rate for the 2nd moment estimates
eps = 1e-8  # A small constant for numerical stability
n_iter = 50
batch_size = 4
loss = np.zeros(n_iter)
plt.figure(figsize=(12,5))
with tf.Session() as sess:
    for i in range(n_iter):
        ind = random.sample(range(X.shape[0]), batch_size)
        loss[i] sess.run(#
        visualize(X[ind,:], y[ind], w, loss, n_iter)
        w = sess.run(#)
visualize(X, y, w, loss, n_iter)
plt.clf()
Explanation: Same task for Adam algorithm. You can start with beta = 0.9 and mu = 0.999
End of explanation
<END_TASK>