import numpy as np


def softmax(predictions):
    """
    Computes probabilities from scores

    Arguments:
      predictions, np array, shape is either (N) or (batch_size, N) -
        classifier output

    Returns:
      probs, np array of the same shape as predictions -
        probability for every class, 0..1
    """
    axis = predictions.ndim - 1
    stab = (predictions.T - np.max(predictions, axis=axis)).T
    exps = np.exp(stab)
    return (exps.T / exps.sum(axis=axis)).T


def cross_entropy_loss(probs, target_index):
    """
    Computes cross-entropy loss

    Arguments:
      probs, np array, shape is either (N) or (batch_size, N) -
        probabilities for every class
      target_index: np array of int, shape is (1) or (batch_size) -
        index of the true class for given sample(s)

    Returns:
      loss: single value
    """
    if probs.ndim == 1:
        idx = target_index
    else:
        idx = (np.arange(probs.shape[0]), target_index)
    return -np.mean(np.log(probs[idx]))


def softmax_with_cross_entropy(predictions, target_index):
    """
    Computes softmax and cross-entropy loss for model predictions,
    including the gradient

    Arguments:
      predictions, np array, shape is either (N) or (batch_size, N) -
        classifier output
      target_index: np array of int, shape is (1) or (batch_size) -
        index of the true class for given sample(s)

    Returns:
      loss, single value - cross-entropy loss
      dprediction, np array same shape as predictions - gradient of predictions by loss value
    """
    probs = softmax(predictions)
    loss = cross_entropy_loss(probs, target_index)

    if probs.ndim == 1:
        n_batches = 1
        idx = target_index
    else:
        n_batches = probs.shape[0]
        idx = (np.arange(n_batches), target_index)

    dprediction = probs
    dprediction[idx] -= 1
    dprediction /= n_batches

    return loss, dprediction


def l2_regularization(W, reg_strength):
    """
    Computes L2 regularization loss on weights and its gradient

    Arguments:
      W, np array - weights
      reg_strength - float value

    Returns:
      loss, single value - l2 regularization loss
      gradient, np.array same shape as W - gradient of weight by l2 loss
    """
    loss = reg_strength * (W ** 2).sum()
    grad = 2 * reg_strength * W
    return loss, grad


def linear_softmax(X, W, target_index):
    """
    Performs linear classification and returns loss and gradient over W

    Arguments:
      X, np array, shape (num_batch, num_features) - batch of images
      W, np array, shape (num_features, classes) - weights
      target_index, np array, shape (num_batch) - index of target classes

    Returns:
      loss, single value - cross-entropy loss
      gradient, np.array same shape as W - gradient of weight by loss

    """
    predictions = X.dot(W)
    loss, dprediction = softmax_with_cross_entropy(predictions, target_index)
    dW = X.T.dot(dprediction)
    return loss, dW


class LinearSoftmaxClassifier:
    def __init__(self):
        self.W = None

    def fit(self, X, y, batch_size=100, learning_rate=1e-7, reg=1e-5,
            epochs=1):
        """
        Trains linear classifier

        Arguments:
          X, np array (num_samples, num_features) - training data
          y, np array of int (num_samples) - labels
          batch_size, int - batch size to use
          learning_rate, float - learning rate for gradient descent
          reg, float - L2 regularization strength
          epochs, int - number of epochs
        """

        num_train = X.shape[0]
        num_features = X.shape[1]
        num_classes = np.max(y) + 1
        if self.W is None:
            self.W = 0.001 * np.random.randn(num_features, num_classes)

        loss_history = []
        for epoch in range(epochs):
            loss = None
            shuffled_indices = np.arange(num_train)
            np.random.shuffle(shuffled_indices)
            sections = np.arange(batch_size, num_train, batch_size)
            batches_indices = np.array_split(shuffled_indices, sections)

            for batch in batches_indices:
                ce_loss, ce_grad = linear_softmax(X[batch], self.W, y[batch])
                reg_loss, reg_grad = l2_regularization(self.W, reg)
                loss, grad = ce_loss + reg_loss, ce_grad + reg_grad
                self.W -= learning_rate * grad
                loss_history.append(loss)

            print("Epoch %i, loss: %f" % (epoch, loss))

        return loss_history

    def predict(self, X):
        """
        Produces classifier predictions on the set

        Arguments:
          X, np array (test_samples, num_features)

        Returns:
          y_pred, np.array of int (test_samples)
        """
        return X.dot(self.W).argmax(axis=1)

import numpy as np


def softmax(predictions):
    """
    Computes probabilities from scores

    Arguments:
      predictions, np array, shape is either (N) or (batch_size, N) -
        classifier output

    Returns:
      probs, np array of the same shape as predictions -
        probability for every class, 0..1
    """
    axis = predictions.ndim - 1
    stab = (predictions.T - np.max(predictions, axis=axis)).T
    exps = np.exp(stab)
    return (exps.T / exps.sum(axis=axis)).T


def cross_entropy_loss(probs, target_index):
    """
    Computes cross-entropy loss

    Arguments:
      probs, np array, shape is either (N) or (batch_size, N) -
        probabilities for every class
      target_index: np array of int, shape is (1) or (batch_size) -
        index of the true class for given sample(s)

    Returns:
      loss: single value
    """
    if probs.ndim == 1:
        idx = target_index
    else:
        idx = (np.arange(probs.shape[0]), target_index)
    return -np.mean(np.log(probs[idx]))


def softmax_with_cross_entropy(predictions, target_index):
    """
    Computes softmax and cross-entropy loss for model predictions,
    including the gradient

    Arguments:
      predictions, np array, shape is either (N) or (batch_size, N) -
        classifier output
      target_index: np array of int, shape is (1) or (batch_size) -
        index of the true class for given sample(s)

    Returns:
      loss, single value - cross-entropy loss
      dprediction, np array same shape as predictions - gradient of predictions by loss value
    """
    probs = softmax(predictions)
    loss = cross_entropy_loss(probs, target_index)

    if probs.ndim == 1:
        n_batches = 1
        idx = target_index
    else:
        n_batches = probs.shape[0]
        idx = (np.arange(n_batches), target_index)

    dprediction = probs
    dprediction[idx] -= 1
    dprediction /= n_batches

    return loss, dprediction


def l2_regularization(W, reg_strength):
    """
    Computes L2 regularization loss on weights and its gradient

    Arguments:
      W, np array - weights
      reg_strength - float value

    Returns:
      loss, single value - l2 regularization loss
      gradient, np.array same shape as W - gradient of weight by l2 loss
    """
    loss = reg_strength * (W ** 2).sum()
    grad = 2 * reg_strength * W
    return loss, grad


def linear_softmax(X, W, target_index):
    """
    Performs linear classification and returns loss and gradient over W

    Arguments:
      X, np array, shape (num_batch, num_features) - batch of images
      W, np array, shape (num_features, classes) - weights
      target_index, np array, shape (num_batch) - index of target classes

    Returns:
      loss, single value - cross-entropy loss
      gradient, np.array same shape as W - gradient of weight by loss

    """
    predictions = X.dot(W)
    loss, dprediction = softmax_with_cross_entropy(predictions, target_index)
    dW = X.T.dot(dprediction)
    return loss, dW


class LinearSoftmaxClassifier:
    def __init__(self):
        self.W = None

    def fit(self, X, y, batch_size=100, learning_rate=1e-7, reg=1e-5,
            epochs=1):
        """
        Trains linear classifier

        Arguments:
          X, np array (num_samples, num_features) - training data
          y, np array of int (num_samples) - labels
          batch_size, int - batch size to use
          learning_rate, float - learning rate for gradient descent
          reg, float - L2 regularization strength
          epochs, int - number of epochs
        """

        num_train = X.shape[0]
        num_features = X.shape[1]
        num_classes = np.max(y) + 1
        if self.W is None:
            self.W = 0.001 * np.random.randn(num_features, num_classes)

        loss_history = []
        for epoch in range(epochs):
            loss = None
            shuffled_indices = np.arange(num_train)
            np.random.shuffle(shuffled_indices)
            sections = np.arange(batch_size, num_train, batch_size)
            batches_indices = np.array_split(shuffled_indices, sections)

            for batch in batches_indices:
                ce_loss, ce_grad = linear_softmax(X[batch], self.W, y[batch])
                reg_loss, reg_grad = l2_regularization(self.W, reg)
                loss, grad = ce_loss + reg_loss, ce_grad + reg_grad
                self.W -= learning_rate * grad
                loss_history.append(loss)

            print("Epoch %i, loss: %f" % (epoch, loss))

        return loss_history

    def predict(self, X):
        """
        Produces classifier predictions on the set

        Arguments:
          X, np array (test_samples, num_features)

        Returns:
          y_pred, np.array of int (test_samples)
        """
        return X.dot(self.W).argmax(axis=1)

Computes probabilities from scores      Arguments:       predictions, np array, shape is either (N) or (batch_size, N) -         classifier output      Returns:       probs, np array of the same shape as predictions -         probability for every class, 0..1 Computes cross-entropy loss      Arguments:       probs, np array, shape is either (N) or (batch_size, N) -         probabilities for every class       target_index: np array of int, shape is (1) or (batch_size) -         index of the true class for given sample(s)      Returns:       loss: single value Computes softmax and cross-entropy loss for model predictions,     including the gradient      Arguments:       predictions, np array, shape is either (N) or (batch_size, N) -         classifier output       target_index: np array of int, shape is (1) or (batch_size) -         index of the true class for given sample(s)      Returns:       loss, single value - cross-entropy loss       dprediction, np array same shape as predictions - gradient of predictions by loss value Computes L2 regularization loss on weights and its gradient      Arguments:       W, np array - weights       reg_strength - float value      Returns:       loss, single value - l2 regularization loss       gradient, np.array same shape as W - gradient of weight by l2 loss Performs linear classification and returns loss and gradient over W      Arguments:       X, np array, shape (num_batch, num_features) - batch of images       W, np array, shape (num_features, classes) - weights       target_index, np array, shape (num_batch) - index of target classes      Returns:       loss, single value - cross-entropy loss       gradient, np.array same shape as W - gradient of weight by loss Trains linear classifier          Arguments:           X, np array (num_samples, num_features) - training data           y, np array of int (num_samples) - labels           batch_size, int - batch size to use           learning_rate, float - learning rate for gradient descent           reg, float - L2 regularization strength           epochs, int - number of epochs Produces classifier predictions on the set          Arguments:           X, np array (test_samples, num_features)          Returns:           y_pred, np.array of int (test_samples)