cs231n Assignment#1 softmax

Softmax exercise

Complete and hand in this completed worksheet (including its outputs and any supporting code outside of the worksheet) with your assignment submission. For more details see the assignments page on the course website.

This exercise is analogous to the SVM exercise. You will:

• implement a fully-vectorized loss function for the Softmax classifier
• implement the fully-vectorized expression for its analytic gradient
• check your implementation with numerical gradient
• use a validation set to tune the learning rate and regularization strength
• optimize the loss function with SGD
• visualize the final learned weights

import random
import numpy as np
from cs231n.data_utils import load_CIFAR10
import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

# for auto-reloading extenrnal modules
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2

def get_CIFAR10_data(num_training=49000, num_validation=1000, num_test=1000, num_dev=500):
  """
  Load the CIFAR-10 dataset from disk and perform preprocessing to prepare
  it for the linear classifier. These are the same steps as we used for the
  SVM, but condensed to a single function.  
  """
  # Load the raw CIFAR-10 data
  cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'
  X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)
  
  # subsample the data
  mask = range(num_training, num_training + num_validation)
  X_val = X_train[mask]
  y_val = y_train[mask]
  mask = range(num_training)
  X_train = X_train[mask]
  y_train = y_train[mask]
  mask = range(num_test)
  X_test = X_test[mask]
  y_test = y_test[mask]
  mask = np.random.choice(num_training, num_dev, replace=False)
  X_dev = X_train[mask]
  y_dev = y_train[mask]
  
  # Preprocessing: reshape the image data into rows
  X_train = np.reshape(X_train, (X_train.shape[0], -1))
  X_val = np.reshape(X_val, (X_val.shape[0], -1))
  X_test = np.reshape(X_test, (X_test.shape[0], -1))
  X_dev = np.reshape(X_dev, (X_dev.shape[0], -1))
  
  # Normalize the data: subtract the mean image
  mean_image = np.mean(X_train, axis = 0)
  X_train -= mean_image
  X_val -= mean_image
  X_test -= mean_image
  X_dev -= mean_image
  
  # add bias dimension and transform into columns
  X_train = np.hstack([X_train, np.ones((X_train.shape[0], 1))])
  X_val = np.hstack([X_val, np.ones((X_val.shape[0], 1))])
  X_test = np.hstack([X_test, np.ones((X_test.shape[0], 1))])
  X_dev = np.hstack([X_dev, np.ones((X_dev.shape[0], 1))])
  
  return X_train, y_train, X_val, y_val, X_test, y_test, X_dev, y_dev


# Invoke the above function to get our data.
X_train, y_train, X_val, y_val, X_test, y_test, X_dev, y_dev = get_CIFAR10_data()
print 'Train data shape: ', X_train.shape
print 'Train labels shape: ', y_train.shape
print 'Validation data shape: ', X_val.shape
print 'Validation labels shape: ', y_val.shape
print 'Test data shape: ', X_test.shape
print 'Test labels shape: ', y_test.shape
print 'dev data shape: ', X_dev.shape
print 'dev labels shape: ', y_dev.shape

Train data shape:  (49000L, 3073L)
Train labels shape:  (49000L,)
Validation data shape:  (1000L, 3073L)
Validation labels shape:  (1000L,)
Test data shape:  (1000L, 3073L)
Test labels shape:  (1000L,)
dev data shape:  (500L, 3073L)
dev labels shape:  (500L,)

Softmax Classifier

Your code for this section will all be written inside cs231n/classifiers/softmax.py.

# First implement the naive softmax loss function with nested loops.
# Open the file cs231n/classifiers/softmax.py and implement the
# softmax_loss_naive function.

from cs231n.classifiers.softmax import softmax_loss_naive
import time

# Generate a random softmax weight matrix and use it to compute the loss.
W = np.random.randn(3073, 10) * 0.0001
loss, grad = softmax_loss_naive(W, X_dev, y_dev, 0.0)

# As a rough sanity check, our loss should be something close to -log(0.1).
print 'loss: %f' % loss
print 'sanity check: %f' % (-np.log(0.1))

loss: 2.395985
sanity check: 2.302585

Inline Question 1:

Why do we expect our loss to be close to -log(0.1)? Explain briefly.

Your answer: Because the W is selected by random, so the probability of select the true class is 1/10. That is, 0.1.

# Complete the implementation of softmax_loss_naive and implement a (naive)
# version of the gradient that uses nested loops.
loss, grad = softmax_loss_naive(W, X_dev, y_dev, 0.0)

# As we did for the SVM, use numeric gradient checking as a debugging tool.
# The numeric gradient should be close to the analytic gradient.
from cs231n.gradient_check import grad_check_sparse
f = lambda w: softmax_loss_naive(w, X_dev, y_dev, 0.0)[0]
grad_numerical = grad_check_sparse(f, W, grad, 10)

# similar to SVM case, do another gradient check with regularization
loss, grad = softmax_loss_naive(W, X_dev, y_dev, 1e2)
f = lambda w: softmax_loss_naive(w, X_dev, y_dev, 1e2)[0]
grad_numerical = grad_check_sparse(f, W, grad, 10)

numerical: 2.368141 analytic: 2.368141, relative error: 2.349797e-08
numerical: 1.324690 analytic: 1.324690, relative error: 7.140560e-08
numerical: 3.170412 analytic: 3.170411, relative error: 1.324741e-08
numerical: 0.249509 analytic: 0.249509, relative error: 2.647240e-08
numerical: 1.536095 analytic: 1.536095, relative error: 4.345856e-08
numerical: 1.075819 analytic: 1.075819, relative error: 3.902323e-08
numerical: -0.198098 analytic: -0.198098, relative error: 5.737134e-08
numerical: -0.089902 analytic: -0.089902, relative error: 8.604010e-07
numerical: -0.339487 analytic: -0.339487, relative error: 3.992996e-08
numerical: -4.819781 analytic: -4.819781, relative error: 3.465667e-09
numerical: 1.869922 analytic: 1.869921, relative error: 7.536693e-08
numerical: 0.783465 analytic: 0.783465, relative error: 6.960291e-08
numerical: -3.206007 analytic: -3.206007, relative error: 2.337350e-09
numerical: 0.532183 analytic: 0.532183, relative error: 1.498128e-07
numerical: 0.900500 analytic: 0.900500, relative error: 6.954913e-09
numerical: -0.353224 analytic: -0.353224, relative error: 1.836960e-07
numerical: -1.331470 analytic: -1.331470, relative error: 2.726426e-08
numerical: -0.082452 analytic: -0.082452, relative error: 7.712355e-07
numerical: -1.322133 analytic: -1.322133, relative error: 5.516628e-09
numerical: 0.345814 analytic: 0.345814, relative error: 1.251858e-07

# Now that we have a naive implementation of the softmax loss function and its gradient,
# implement a vectorized version in softmax_loss_vectorized.
# The two versions should compute the same results, but the vectorized version should be
# much faster.
tic = time.time()
loss_naive, grad_naive = softmax_loss_naive(W, X_dev, y_dev, 0.00001)
toc = time.time()
print 'naive loss: %e computed in %fs' % (loss_naive, toc - tic)

from cs231n.classifiers.softmax import softmax_loss_vectorized
tic = time.time()
loss_vectorized, grad_vectorized = softmax_loss_vectorized(W, X_dev, y_dev, 0.00001)
toc = time.time()
print 'vectorized loss: %e computed in %fs' % (loss_vectorized, toc - tic)

# As we did for the SVM, we use the Frobenius norm to compare the two versions
# of the gradient.
grad_difference = np.linalg.norm(grad_naive - grad_vectorized, ord='fro')
print 'Loss difference: %f' % np.abs(loss_naive - loss_vectorized)
print 'Gradient difference: %f' % grad_difference

naive loss: 2.395985e+00 computed in 0.080000s
vectorized loss: 2.395985e+00 computed in 0.003000s
Loss difference: 0.000000
Gradient difference: 0.000000

# Use the validation set to tune hyperparameters (regularization strength and
# learning rate). You should experiment with different ranges for the learning
# rates and regularization strengths; if you are careful you should be able to
# get a classification accuracy of over 0.35 on the validation set.
from cs231n.classifiers import Softmax
results = {}
best_val = -1
best_softmax = None
learning_rates = [1e-8, 1e-7, 2e-7]
regularization_strengths = [1e4, 2e4, 3e4, 4e4, 5e4, 6e4, 7e4, 8e4, 1e5]

################################################################################
# TODO:                                                                        #
# Use the validation set to set the learning rate and regularization strength. #
# This should be identical to the validation that you did for the SVM; save    #
# the best trained softmax classifer in best_softmax.                          #
################################################################################
iters = 2000
for lr in learning_rates:
    for rs in regularization_strengths:
        softmax = Softmax()
        softmax.train(X_train, y_train, learning_rate=lr, reg=rs, num_iters=iters)
        
        y_train_pred = softmax.predict(X_train)
        acc_train = np.mean(y_train == y_train_pred)
        y_val_pred = softmax.predict(X_val)
        acc_val = np.mean(y_val == y_val_pred)
        
        results[(lr, rs)] = (acc_train, acc_val)
        
        if best_val < acc_val:
            best_val = acc_val
            best_softmax = softmax
################################################################################
#                              END OF YOUR CODE                                #
################################################################################
    
# Print out results.
for lr, reg in sorted(results):
    train_accuracy, val_accuracy = results[(lr, reg)]
    print 'lr %e reg %e train accuracy: %f val accuracy: %f' % (
                lr, reg, train_accuracy, val_accuracy)
    
print 'best validation accuracy achieved during cross-validation: %f' % best_val

lr 1.000000e-08 reg 1.000000e+04 train accuracy: 0.175633 val accuracy: 0.179000
lr 1.000000e-08 reg 2.000000e+04 train accuracy: 0.174102 val accuracy: 0.161000
lr 1.000000e-08 reg 3.000000e+04 train accuracy: 0.203490 val accuracy: 0.210000
lr 1.000000e-08 reg 4.000000e+04 train accuracy: 0.191367 val accuracy: 0.202000
lr 1.000000e-08 reg 5.000000e+04 train accuracy: 0.208000 val accuracy: 0.197000
lr 1.000000e-08 reg 6.000000e+04 train accuracy: 0.203571 val accuracy: 0.215000
lr 1.000000e-08 reg 7.000000e+04 train accuracy: 0.213551 val accuracy: 0.215000
lr 1.000000e-08 reg 8.000000e+04 train accuracy: 0.238347 val accuracy: 0.229000
lr 1.000000e-08 reg 1.000000e+05 train accuracy: 0.245102 val accuracy: 0.242000
lr 1.000000e-07 reg 1.000000e+04 train accuracy: 0.358265 val accuracy: 0.362000
lr 1.000000e-07 reg 2.000000e+04 train accuracy: 0.356306 val accuracy: 0.374000
lr 1.000000e-07 reg 3.000000e+04 train accuracy: 0.347327 val accuracy: 0.362000
lr 1.000000e-07 reg 4.000000e+04 train accuracy: 0.336347 val accuracy: 0.354000
lr 1.000000e-07 reg 5.000000e+04 train accuracy: 0.331490 val accuracy: 0.348000
lr 1.000000e-07 reg 6.000000e+04 train accuracy: 0.320163 val accuracy: 0.336000
lr 1.000000e-07 reg 7.000000e+04 train accuracy: 0.314551 val accuracy: 0.325000
lr 1.000000e-07 reg 8.000000e+04 train accuracy: 0.313082 val accuracy: 0.324000
lr 1.000000e-07 reg 1.000000e+05 train accuracy: 0.303000 val accuracy: 0.315000
lr 2.000000e-07 reg 1.000000e+04 train accuracy: 0.374163 val accuracy: 0.389000
lr 2.000000e-07 reg 2.000000e+04 train accuracy: 0.353184 val accuracy: 0.365000
lr 2.000000e-07 reg 3.000000e+04 train accuracy: 0.340265 val accuracy: 0.359000
lr 2.000000e-07 reg 4.000000e+04 train accuracy: 0.334673 val accuracy: 0.351000
lr 2.000000e-07 reg 5.000000e+04 train accuracy: 0.326531 val accuracy: 0.337000
lr 2.000000e-07 reg 6.000000e+04 train accuracy: 0.319857 val accuracy: 0.336000
lr 2.000000e-07 reg 7.000000e+04 train accuracy: 0.317878 val accuracy: 0.329000
lr 2.000000e-07 reg 8.000000e+04 train accuracy: 0.310449 val accuracy: 0.329000
lr 2.000000e-07 reg 1.000000e+05 train accuracy: 0.316286 val accuracy: 0.315000
best validation accuracy achieved during cross-validation: 0.389000

# evaluate on test set
# Evaluate the best softmax on test set
y_test_pred = best_softmax.predict(X_test)
test_accuracy = np.mean(y_test == y_test_pred)
print 'softmax on raw pixels final test set accuracy: %f' % (test_accuracy, )

softmax on raw pixels final test set accuracy: 0.375000

​

# Visualize the learned weights for each class
w = best_softmax.W[:-1,:] # strip out the bias
w = w.reshape(32, 32, 3, 10)

w_min, w_max = np.min(w), np.max(w)

classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
for i in xrange(10):
  plt.subplot(2, 5, i + 1)
  
  # Rescale the weights to be between 0 and 255
  wimg = 255.0 * (w[:, :, :, i].squeeze() - w_min) / (w_max - w_min)
  plt.imshow(wimg.astype('uint8'))
  plt.axis('off')
  plt.title(classes[i])

Codes

import numpy as np
from random import shuffle


def softmax_loss_naive(W, X, y, reg):
    """
    Softmax loss function, naive implementation (with loops)

    Inputs have dimension D, there are C classes, and we operate on minibatches
    of N examples.

    Inputs:
    - W: A numpy array of shape (D, C) containing weights.
    - X: A numpy array of shape (N, D) containing a minibatch of data.
    - y: A numpy array of shape (N,) containing training labels; y[i] = c means
      that X[i] has label c, where 0 <= c < C.
    - reg: (float) regularization strength

    Returns a tuple of:
    - loss as single float
    - gradient with respect to weights W; an array of same shape as W
    """
    # Initialize the loss and gradient to zero.
    loss = 0.0
    dW = np.zeros_like(W)

    #############################################################################
    # TODO: Compute the softmax loss and its gradient using explicit loops.     #
    # Store the loss in loss and the gradient in dW. If you are not careful     #
    # here, it is easy to run into numeric instability. Don't forget the        #
    # regularization!                                                           #
    #############################################################################
    num_train = X.shape[0]
    num_classes = W.shape[1]

    for i in xrange(num_train):
        f = X[i, :].dot(W)
        f -= np.max(f)
        correct_f = f[y[i]]
        denom = np.sum(np.exp(f))

        p = np.exp(correct_f) / denom
        loss += -np.log(p)

        for j in xrange(num_classes):
            if j == y[i]:
                dW[:, y[i]] += (np.exp(f[j]) / denom - 1) * X[i, :]
            else:
                dW[:, j] += (np.exp(f[j]) / denom) * X[i, :]

    loss /= num_train
    loss += 0.5 * reg * np.sum(W * W)

    dW /= num_train
    dW += reg * W
    #############################################################################
    #                          END OF YOUR CODE                                 #
    #############################################################################

    return loss, dW


def softmax_loss_vectorized(W, X, y, reg):
    """
    Softmax loss function, vectorized version.

    Inputs and outputs are the same as softmax_loss_naive.
    """
    # Initialize the loss and gradient to zero.
    loss = 0.0
    dW = np.zeros_like(W)

    #############################################################################
    # TODO: Compute the softmax loss and its gradient using no explicit loops.  #
    # Store the loss in loss and the gradient in dW. If you are not careful     #
    # here, it is easy to run into numeric instability. Don't forget the        #
    # regularization!                                                           #
    #############################################################################
    num_train = X.shape[0]

    f = X.dot(W)
    f = f - np.max(f, axis=1)[:, np.newaxis]
    loss = -np.sum(
        np.log(np.exp(f[np.arange(num_train), y]) / np.sum(np.exp(f), axis=1)))

    loss /= num_train
    loss += 0.5 * reg * np.sum(W * W)

    ind = np.zeros_like(f)
    ind[np.arange(num_train), y] = 1
    dW = X.T.dot(np.exp(f) / np.sum(np.exp(f), axis=1, keepdims=True) - ind)

    dW /= num_train
    dW += reg * W
    #############################################################################
    #                          END OF YOUR CODE                                 #
    #############################################################################

    return loss, dW