# -*- coding: utf-8 -*-

import matplotlib.pyplot as plt

'''同路径下py模块引用'''

try:

    from . import data_utils

    from . import solver

    from . import cnn

except Exception:

    import data_utils

    import solver

    import cnn

import numpy as np

# 获取样本数据

data = data_utils.get_CIFAR10_data()

# model初始化（权重因子以及对应偏置 w1,b1 ,w2,b2 ,w3,b3，数量取决于网络层数）

model = cnn.ThreeLayerConvNet(reg=0.9)

solver = solver.Solver(model, data,

                lr_decay=0.95,

                print_every=10, num_epochs=5, batch_size=2,

                update_rule='sgd_momentum',

                optim_config={'learning_rate': 5e-4, 'momentum': 0.9})

# 训练，获取最佳model

solver.train()                 

plt.subplot(2, 1, 1)

plt.title('Training loss')

plt.plot(solver.loss_history, 'o')

plt.xlabel('Iteration')

plt.subplot(2, 1, 2)

plt.title('Accuracy')

plt.plot(solver.train_acc_history, '-o', label='train')

plt.plot(solver.val_acc_history, '-o', label='val')

plt.plot([0.5] * len(solver.val_acc_history), 'k--')

plt.xlabel('Epoch')

plt.legend(loc='lower right')

plt.gcf().set_size_inches(15, 12)

plt.show()

best_model = model

y_test_pred = np.argmax(best_model.loss(data['X_test']), axis=1)

y_val_pred = np.argmax(best_model.loss(data['X_val']), axis=1)

print ('Validation set accuracy: ',(y_val_pred == data['y_val']).mean())

print ('Test set accuracy: ', (y_test_pred == data['y_test']).mean())

# Validation set accuracy:  about 52.9%

# Test set accuracy:  about 54.7%

# Visualize the weights of the best network

"""

from vis_utils import visualize_grid

def show_net_weights(net):

    W1 = net.params['W1']

    W1 = W1.reshape(3, 32, 32, -1).transpose(3, 1, 2, 0)

    plt.imshow(visualize_grid(W1, padding=3).astype('uint8'))

    plt.gca().axis('off')

show_net_weights(best_model)

plt.show()

"""

# -*- coding: utf-8 -*-

try:

    from . import layer_utils

    from . import layers

except Exception:

    import layer_utils

    import layers

import numpy as np

class  ThreeLayerConvNet(object):

    """

    A three-layer convolutional network with the following architecture:

       conv - relu - 2x2 max pool - affine - relu - affine - softmax

    """

    def __init__(self, input_dim=(3, 32, 32), num_filters=32, filter_size=7,

                 hidden_dim=100, num_classes=10, weight_scale=1e-3, reg=0.0,

                 dtype=np.float32):

        self.params = {}

        self.reg = reg

        self.dtype = dtype

        # Initialize weights and biases

        C, H, W = input_dim

        self.params['W1'] = weight_scale * np.random.randn(num_filters, C, filter_size, filter_size)

        self.params['b1'] = np.zeros(num_filters)

        self.params['W2'] = weight_scale * np.random.randn(num_filters*H*W//4, hidden_dim)

        self.params['b2'] = np.zeros(hidden_dim)

        self.params['W3'] = weight_scale * np.random.randn(hidden_dim, num_classes)

        self.params['b3'] = np.zeros(num_classes)

        for k, v in self.params.items():

            self.params[k] = v.astype(dtype)

    def loss(self, X, y=None):

        W1, b1 = self.params['W1'], self.params['b1']

        W2, b2 = self.params['W2'], self.params['b2']

        W3, b3 = self.params['W3'], self.params['b3']

        # pass conv_param to the forward pass for the convolutional layer

        filter_size = W1.shape[2]

        conv_param = {'stride': 1, 'pad': (filter_size - 1) // 2}

        # pass pool_param to the forward pass for the max-pooling layer

        pool_param = {'pool_height': 2, 'pool_width': 2, 'stride': 2}

        # compute the forward pass

        a1, cache1 = layer_utils.conv_relu_pool_forward(X, W1, b1, conv_param, pool_param)

        a2, cache2 = layer_utils.affine_relu_forward(a1, W2, b2)

        scores, cache3 = layers.affine_forward(a2, W3, b3)

        if y is None:

            return scores

        # compute the backward pass

        data_loss, dscores = layers.softmax_loss(scores, y)

        da2, dW3, db3 = layers.affine_backward(dscores, cache3)

        da1, dW2, db2 = layer_utils.affine_relu_backward(da2, cache2)

        dX, dW1, db1 = layer_utils.conv_relu_pool_backward(da1, cache1)

        # Add regularization 引入修正因子，重新计算损失，梯度

        dW1 += self.reg * W1

        dW2 += self.reg * W2

        dW3 += self.reg * W3

        reg_loss = 0.5 * self.reg * sum(np.sum(W * W) for W in [W1, W2, W3])

        loss = data_loss + reg_loss

        grads = {'W1': dW1, 'b1': db1, 'W2': dW2, 'b2': db2, 'W3': dW3, 'b3': db3}

        return loss, grads

# -*- coding: utf-8 -*-

import pickle

import numpy as np

import os

#from scipy.misc import imread

def load_CIFAR_batch(filename):

  """ load single batch of cifar """

  with open(filename, 'rb') as f:

    datadict = pickle.load(f, encoding='bytes')

    X = datadict[b'data']

    Y = datadict[b'labels']

    X = X.reshape(10000, 3, 32, 32).transpose(0,2,3,1).astype("float")

    Y = np.array(Y)

    return X, Y

def load_CIFAR10(ROOT):

  """ load all of cifar """

  xs = []

  ys = []

  for b in range(1,2):

    f = os.path.join(ROOT, 'data_batch_%d' % (b, ))

    X, Y = load_CIFAR_batch(f)

    xs.append(X)

    ys.append(Y)

  Xtr = np.concatenate(xs)

  Ytr = np.concatenate(ys)

  del X, Y

  Xte, Yte = load_CIFAR_batch(os.path.join(ROOT, 'test_batch'))

  return Xtr, Ytr, Xte, Yte

def get_CIFAR10_data(num_training=500, num_validation=50, num_test=50):

    """

    Load the CIFAR-10 dataset from disk and perform preprocessing to prepare

    it for classifiers. 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 = 'C://download//cifar-10-python//cifar-10-batches-py//'

    cifar10_dir = '.\\cifar-10-batches-py\\'

    X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)

    print (X_train.shape)

    # 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]

    # 标准化数据，求样本均值，然后 样本 - 样本均值，作用：使样本数据更收敛一些，便于后续处理

    # Normalize the data: subtract the mean image

    # 如果2维空间 m*n np.mean()后 => 1*n

    # 对于4维空间 m*n*k*j np.mean()后 => 1*n*k*j

    mean_image = np.mean(X_train, axis=0)

    X_train -= mean_image

    X_val -= mean_image

    X_test -= mean_image

    # 把通道channel 提前

    # Transpose so that channels come first

    X_train = X_train.transpose(0, 3, 1, 2).copy()

    X_val = X_val.transpose(0, 3, 1, 2).copy()

    X_test = X_test.transpose(0, 3, 1, 2).copy()

    # Package data into a dictionary

    return {

      'X_train': X_train, 'y_train': y_train,

      'X_val': X_val, 'y_val': y_val,

      'X_test': X_test, 'y_test': y_test,

    }

"""

def load_tiny_imagenet(path, dtype=np.float32):

  Load TinyImageNet. Each of TinyImageNet-100-A, TinyImageNet-100-B, and

  TinyImageNet-200 have the same directory structure, so this can be used

  to load any of them.

  Inputs:

  - path: String giving path to the directory to load.

  - dtype: numpy datatype used to load the data.

  Returns: A tuple of

  - class_names: A list where class_names[i] is a list of strings giving the

    WordNet names for class i in the loaded dataset.

  - X_train: (N_tr, 3, 64, 64) array of training images

  - y_train: (N_tr,) array of training labels

  - X_val: (N_val, 3, 64, 64) array of validation images

  - y_val: (N_val,) array of validation labels

  - X_test: (N_test, 3, 64, 64) array of testing images.

  - y_test: (N_test,) array of test labels; if test labels are not available

    (such as in student code) then y_test will be None.

  # First load wnids

  with open(os.path.join(path, 'wnids.txt'), 'r') as f:

    wnids = [x.strip() for x in f]

  # Map wnids to integer labels

  wnid_to_label = {wnid: i for i, wnid in enumerate(wnids)}

  # Use words.txt to get names for each class

  with open(os.path.join(path, 'words.txt'), 'r') as f:

    wnid_to_words = dict(line.split('\t') for line in f)

    for wnid, words in wnid_to_words.iteritems():

      wnid_to_words[wnid] = [w.strip() for w in words.split(',')]

  class_names = [wnid_to_words[wnid] for wnid in wnids]

  # Next load training data.

  X_train = []

  y_train = []

  for i, wnid in enumerate(wnids):

    if (i + 1) % 20 == 0:

      print 'loading training data for synset %d / %d' % (i + 1, len(wnids))

    # To figure out the filenames we need to open the boxes file

    boxes_file = os.path.join(path, 'train', wnid, '%s_boxes.txt' % wnid)

    with open(boxes_file, 'r') as f:

      filenames = [x.split('\t')[0] for x in f]

    num_images = len(filenames)

    X_train_block = np.zeros((num_images, 3, 64, 64), dtype=dtype)

    y_train_block = wnid_to_label[wnid] * np.ones(num_images, dtype=np.int64)

    for j, img_file in enumerate(filenames):

      img_file = os.path.join(path, 'train', wnid, 'images', img_file)

      img = imread(img_file)

      if img.ndim == 2:

        ## grayscale file

        img.shape = (64, 64, 1)

      X_train_block[j] = img.transpose(2, 0, 1)

    X_train.append(X_train_block)

    y_train.append(y_train_block)

  # We need to concatenate all training data

  X_train = np.concatenate(X_train, axis=0)

  y_train = np.concatenate(y_train, axis=0)

  # Next load validation data

  with open(os.path.join(path, 'val', 'val_annotations.txt'), 'r') as f:

    img_files = []

    val_wnids = []

    for line in f:

      img_file, wnid = line.split('\t')[:2]

      img_files.append(img_file)

      val_wnids.append(wnid)

    num_val = len(img_files)

    y_val = np.array([wnid_to_label[wnid] for wnid in val_wnids])

    X_val = np.zeros((num_val, 3, 64, 64), dtype=dtype)

    for i, img_file in enumerate(img_files):

      img_file = os.path.join(path, 'val', 'images', img_file)

      img = imread(img_file)

      if img.ndim == 2:

        img.shape = (64, 64, 1)

      X_val[i] = img.transpose(2, 0, 1)

  # Next load test images

  # Students won't have test labels, so we need to iterate over files in the

  # images directory.

  img_files = os.listdir(os.path.join(path, 'test', 'images'))

  X_test = np.zeros((len(img_files), 3, 64, 64), dtype=dtype)

  for i, img_file in enumerate(img_files):

    img_file = os.path.join(path, 'test', 'images', img_file)

    img = imread(img_file)

    if img.ndim == 2:

      img.shape = (64, 64, 1)

    X_test[i] = img.transpose(2, 0, 1)

  y_test = None

  y_test_file = os.path.join(path, 'test', 'test_annotations.txt')

  if os.path.isfile(y_test_file):

    with open(y_test_file, 'r') as f:

      img_file_to_wnid = {}

      for line in f:

        line = line.split('\t')

        img_file_to_wnid[line[0]] = line[1]

    y_test = [wnid_to_label[img_file_to_wnid[img_file]] for img_file in img_files]

    y_test = np.array(y_test)

  return class_names, X_train, y_train, X_val, y_val, X_test, y_test

"""

def load_models(models_dir):

  """

  Load saved models from disk. This will attempt to unpickle all files in a

  directory; any files that give errors on unpickling (such as README.txt) will

  be skipped.

  Inputs:

  - models_dir: String giving the path to a directory containing model files.

    Each model file is a pickled dictionary with a 'model' field.

  Returns:

  A dictionary mapping model file names to models.

  """

  models = {}

  for model_file in os.listdir(models_dir):

    with open(os.path.join(models_dir, model_file), 'rb') as f:

      try:

        models[model_file] = pickle.load(f)['model']

      except pickle.UnpicklingError:

        continue

  return models

# -*- coding: utf-8 -*-

try:

  from . import layers

except Exception:

  import layers

def affine_relu_forward(x, w, b):

  """

  Convenience layer that perorms an affine transform followed by a ReLU

  Inputs:

  - x: Input to the affine layer

  - w, b: Weights for the affine layer

  Returns a tuple of:

  - out: Output from the ReLU

  - cache: Object to give to the backward pass

  """

  a, fc_cache = layers.affine_forward(x, w, b)

  out, relu_cache = layers.relu_forward(a)

  cache = (fc_cache, relu_cache)

  return out, cache

def affine_relu_backward(dout, cache):

  """

  Backward pass for the affine-relu convenience layer

  """

  fc_cache, relu_cache = cache

  da = layers.relu_backward(dout, relu_cache)

  dx, dw, db = layers.affine_backward(da, fc_cache)

  return dx, dw, db

pass

def conv_relu_forward(x, w, b, conv_param):

  """

  A convenience layer that performs a convolution followed by a ReLU.

  Inputs:

  - x: Input to the convolutional layer

  - w, b, conv_param: Weights and parameters for the convolutional layer

  Returns a tuple of:

  - out: Output from the ReLU

  - cache: Object to give to the backward pass

  """

  a, conv_cache = layers.conv_forward_fast(x, w, b, conv_param)

  out, relu_cache = layers.relu_forward(a)

  cache = (conv_cache, relu_cache)

  return out, cache

def conv_relu_backward(dout, cache):

  """

  Backward pass for the conv-relu convenience layer.

  """

  conv_cache, relu_cache = cache

  da = layers.relu_backward(dout, relu_cache)

  dx, dw, db = layers.conv_backward_fast(da, conv_cache)

  return dx, dw, db

def conv_relu_pool_forward(x, w, b, conv_param, pool_param):

  """

  Convenience layer that performs a convolution, a ReLU, and a pool.

  Inputs:

  - x: Input to the convolutional layer

  - w, b, conv_param: Weights and parameters for the convolutional layer

  - pool_param: Parameters for the pooling layer

  Returns a tuple of:

  - out: Output from the pooling layer

  - cache: Object to give to the backward pass

  """

  a, conv_cache = layers.conv_forward_naive(x, w, b, conv_param)

  s, relu_cache = layers.relu_forward(a)

  out, pool_cache = layers.max_pool_forward_naive(s, pool_param)

  cache = (conv_cache, relu_cache, pool_cache)

  return out, cache

def conv_relu_pool_backward(dout, cache):

  """

  Backward pass for the conv-relu-pool convenience layer

  """

  conv_cache, relu_cache, pool_cache = cache

  ds = layers.max_pool_backward_naive(dout, pool_cache)

  da = layers.relu_backward(ds, relu_cache)

  dx, dw, db = layers.conv_backward_naive(da, conv_cache)

  return dx, dw, db

import numpy as np

'''

全连接层：矩阵变换，获取对应目标相同的行与列

输入x: 2*32*16*16

输入x_row: 2*8192

超参w：8192*100

输出：矩阵乘法 2*8192 ->8192*100 =>2*100

'''

def affine_forward(x, w, b):

    """

    Computes the forward pass for an affine (fully-connected) layer.

    The input x has shape (N, d_1, ..., d_k) and contains a minibatch of N

    examples, where each example x[i] has shape (d_1, ..., d_k). We will

    reshape each input into a vector of dimension D = d_1 * ... * d_k, and

    then transform it to an output vector of dimension M.

    Inputs:

    - x: A numpy array containing input data, of shape (N, d_1, ..., d_k)

    - w: A numpy array of weights, of shape (D, M)

    - b: A numpy array of biases, of shape (M,)

    Returns a tuple of:

    - out: output, of shape (N, M)

    - cache: (x, w, b)

    """

    out = None

    # Reshape x into rows

    N = x.shape[0]

    x_row = x.reshape(N, -1)         # (N,D) -1表示不知道多少列，指定行，就能算出列 = 2 * 32 * 16 * 16/2 = 8192

    out = np.dot(x_row, w) + b       # (N,M) 2*8192 8192*100 =>2 * 100

    cache = (x, w, b)

    return out, cache

'''

反向传播之affine矩阵变换

根据dout求出dx,dw,db

由 out = w * x =>

dx = dout * w

dw = dout * x

db = dout * 1

因为dx 与 x，dw 与 w，db 与 b 大小（维度）必须相同

dx = dout * wT  矩阵乘法

dw = dxT * dout 矩阵乘法

db = dout 按列求和

'''

def affine_backward(dout, cache):

    """

    Computes the backward pass for an affine layer.

    Inputs:

    - dout: Upstream derivative, of shape (N, M)

    - cache: Tuple of:

    - x: Input data, of shape (N, d_1, ... d_k)

    - w: Weights, of shape (D, M)

    Returns a tuple of:

    - dx: Gradient with respect to x, of shape (N, d1, ..., d_k)

      dx = dout * w

    - dw: Gradient with respect to w, of shape (D, M)

      dw = dout * x

    - db: Gradient with respect to b, of shape (M,)

      db = dout * 1

    """

    x, w, b = cache

    dx, dw, db = None, None, None

    dx = np.dot(dout, w.T)                       # (N,D)

    # dx维度必须跟x维度相同

    dx = np.reshape(dx, x.shape)                 # (N,d1,...,d_k)

    # 转换成二维矩阵

    x_row = x.reshape(x.shape[0], -1)            # (N,D)

    dw = np.dot(x_row.T, dout)                   # (D,M)

    db = np.sum(dout, axis=0, keepdims=True)     # (1,M)    

    return dx, dw, db

def relu_forward(x):

    """ 激活函数，解决sigmoid梯度消失问题，网络性能比sigmoid更好

    Computes the forward pass for a layer of rectified linear units (ReLUs).

    Input:

    - x: Inputs, of any shape

    Returns a tuple of:

    - out: Output, of the same shape as x

    - cache: x

    """

    out = None

    out = ReLU(x)

    cache = x    

    return out, cache

def relu_backward(dout, cache):

    """

    Computes the backward pass for a layer of rectified linear units (ReLUs).

    Input:

    - dout: Upstream derivatives, of any shape

    - cache: Input x, of same shape as dout

    Returns:

    - dx: Gradient with respect to x

    """

    dx, x = None, cache

    dx = dout

    dx[x <= 0] = 0    

    return dx

def svm_loss(x, y):

    """

    Computes the loss and gradient using for multiclass SVM classification.

    Inputs:

    - x: Input data, of shape (N, C) where x[i, j] is the score for the jth class

         for the ith input.

    - y: Vector of labels, of shape (N,) where y[i] is the label for x[i] and

         0 <= y[i] < C

    Returns a tuple of:

    - loss: Scalar giving the loss

    - dx: Gradient of the loss with respect to x

    """

    N = x.shape[0]

    correct_class_scores = x[np.arange(N), y]

    margins = np.maximum(0, x - correct_class_scores[:, np.newaxis] + 1.0)

    margins[np.arange(N), y] = 0

    loss = np.sum(margins) / N

    num_pos = np.sum(margins > 0, axis=1)

    dx = np.zeros_like(x)

    dx[margins > 0] = 1

    dx[np.arange(N), y] -= num_pos

    dx /= N    

    return loss, dx

'''

softmax_loss 求梯度优点: 求梯度运算简单，方便

softmax: softmax用于多分类过程中，它将多个神经元的输出，映射到（0,1）区间内，

可以看成概率来理解，从而来进行多分类。

Si = exp(i)/[exp(j)求和]

softmax_loss：损失函数，求梯度dx必须用到损失函数，通过梯度下降更新超参

Loss = -[Ypred*ln(Sj真实类别位置的概率值)]求和

梯度dx : 对损失函数求一阶偏导

如果 j = i =>dx = Sj - 1

如果 j != i => dx = Sj

'''

def softmax_loss(x, y):

    """

    Computes the loss and gradient for softmax classification.    Inputs:

    - x: Input data, of shape (N, C) where x[i, j] is the score for the jth class

    for the ith input.

    - y: Vector of labels, of shape (N,) where y[i] is the label for x[i] and

         0 <= y[i] < C

    Returns a tuple of:

    - loss: Scalar giving the loss

    - dx: Gradient of the loss with respect to x

    """

    '''

     x - np.max(x, axis=1, keepdims=True) 对数据进行预处理，

     防止np.exp(x - np.max(x, axis=1, keepdims=True))得到结果太分散；

     np.max(x, axis=1, keepdims=True)保证所得结果维度不变；

    '''

    probs = np.exp(x - np.max(x, axis=1, keepdims=True))

    # 计算softmax，准确的说应该是soft，因为还没有选取概率最大值的操作

    probs /= np.sum(probs, axis=1, keepdims=True)

    # 样本图片个数

    N = x.shape[0]

    # 计算图片损失

    loss = -np.sum(np.log(probs[np.arange(N), y])) / N

    # 复制概率

    dx = probs.copy()

    # 针对 i = j 求梯度

    dx[np.arange(N), y] -= 1

    # 计算每张样本图片梯度

    dx /= N    

    return loss, dx

def ReLU(x):

    """ReLU non-linearity."""

    return np.maximum(0, x)

'''

功能：获取图片特征

前向卷积：每次用一个3维的卷积核与图片RGB各个通道分别卷积（卷积核1与R进行点积，卷积核2与G点积，卷积核3与B点积）,

然后将3个结果求和（也就是 w*x ）,再加上 b，就是新结果某一位置输出，这是卷积核在图片某一固定小范围内（卷积核大小）的卷积，

要想获得整个图片的卷积结果，需要在图片上滑动卷积核（先右后下），直至遍历整个图片。

x: 2*3*32*32  每次选取2张图片，图片大小32*32，彩色(3通道)

w: 32*3*7*7   卷积核每个大小是7*7；对应输入x的3通道，所以是3维，有32个卷积核

pad = 3(图片边缘行列补0)，stride = 1(卷积核移动步长)

输出宽*高结果：(32-7+2*3)/1 + 1 = 32

输出大小：2*32*32*32

'''

def conv_forward_naive(x, w, b, conv_param):

    stride, pad = conv_param['stride'], conv_param['pad']

    N, C, H, W = x.shape

    F, C, HH, WW = w.shape

    x_padded = np.pad(x, ((0, 0), (0, 0), (pad, pad), (pad, pad)), mode='constant')

    '''// : 求整型'''

    H_new = 1 + (H + 2 * pad - HH) // stride

    W_new = 1 + (W + 2 * pad - WW) // stride

    s = stride

    out = np.zeros((N, F, H_new, W_new))

    for i in range(N):       # ith image

        for f in range(F):   # fth filter

            for j in range(H_new):

                for k in range(W_new):

                    #print x_padded[i, :, j*s:HH+j*s, k*s:WW+k*s].shape

                    #print w[f].shape

                    #print b.shape

                    #print np.sum((x_padded[i, :, j*s:HH+j*s, k*s:WW+k*s] * w[f]))

                    out[i, f, j, k] = np.sum(x_padded[i, :, j*s:HH+j*s, k*s:WW+k*s] * w[f]) + b[f]

    cache = (x, w, b, conv_param)

    return out, cache

'''

反向传播之卷积：卷积核3*7*7

输入dout:2*32*32*32

输出dx:2*3*32*32

'''

def conv_backward_naive(dout, cache):

    x, w, b, conv_param = cache

    # 边界补0

    pad = conv_param['pad']

    # 步长

    stride = conv_param['stride']

    F, C, HH, WW = w.shape

    N, C, H, W = x.shape

    H_new = 1 + (H + 2 * pad - HH) // stride

    W_new = 1 + (W + 2 * pad - WW) // stride

    dx = np.zeros_like(x)

    dw = np.zeros_like(w)

    db = np.zeros_like(b)

    s = stride

    x_padded = np.pad(x, ((0, 0), (0, 0), (pad, pad), (pad, pad)), 'constant')

    dx_padded = np.pad(dx, ((0, 0), (0, 0), (pad, pad), (pad, pad)), 'constant')

    # 图片个数

    for i in range(N):       # ith image

        # 卷积核滤波个数

        for f in range(F):   # fth filter

            for j in range(H_new):

                for k in range(W_new):

                    # 3*7*7

                    window = x_padded[i, :, j*s:HH+j*s, k*s:WW+k*s]

                    db[f] += dout[i, f, j, k]

                    # 3*7*7

                    dw[f] += window * dout[i, f, j, k]

                    # 3*7*7 => 2*3*38*38

                    dx_padded[i, :, j*s:HH+j*s, k*s:WW+k*s] += w[f] * dout[i, f, j, k]

    # Unpad

    dx = dx_padded[:, :, pad:pad+H, pad:pad+W]

    return dx, dw, db

'''

功能：减少特征尺寸大小

前向最大池化：在特征矩阵中选取指定大小窗口，获取窗口内元素最大值作为输出窗口映射值，

先有后下遍历，直至获取整个特征矩阵对应的新映射特征矩阵。

输入x：2*32*32*32

池化参数：窗口：2*2，步长：2

输出窗口宽，高：(32-2)/2 + 1 = 16

输出大小：2*32*16*16

'''

def max_pool_forward_naive(x, pool_param):

    HH, WW = pool_param['pool_height'], pool_param['pool_width']

    s = pool_param['stride']

    N, C, H, W = x.shape

    H_new = 1 + (H - HH) // s

    W_new = 1 + (W - WW) // s

    out = np.zeros((N, C, H_new, W_new))

    for i in range(N):

        for j in range(C):

            for k in range(H_new):

                for l in range(W_new):

                    window = x[i, j, k*s:HH+k*s, l*s:WW+l*s]

                    out[i, j, k, l] = np.max(window)

    cache = (x, pool_param)

    return out, cache

'''

反向传播之池化：增大特征尺寸大小

在缓存中取出前向池化时输入特征，选取某一范围矩阵窗口，

找出最大值所在的位置，根据这个位置将dout值映射到新的矩阵对应位置上，

而新矩阵其他位置都初始化为0.

输入dout:2*32*16*16

输出dx:2*32*32*32

'''

def max_pool_backward_naive(dout, cache):

    x, pool_param = cache

    HH, WW = pool_param['pool_height'], pool_param['pool_width']

    s = pool_param['stride']

    N, C, H, W = x.shape

    H_new = 1 + (H - HH) // s

    W_new = 1 + (W - WW) // s

    dx = np.zeros_like(x)

    for i in range(N):

        for j in range(C):

            for k in range(H_new):

                for l in range(W_new):

                    # 取前向传播时输入的某一池化窗口

                    window = x[i, j, k*s:HH+k*s, l*s:WW+l*s]

                    # 计算窗口最大值

                    m = np.max(window)

                    # 根据最大值所在位置以及dout对应值=>新矩阵窗口数值

                    # [false,false

                    #  true, false]  * 1 => [0,0

                    #                        1,0]

                    dx[i, j, k*s:HH+k*s, l*s:WW+l*s] = (window == m) * dout[i, j, k, l]

    return dx

import numpy as np

def sgd(w, dw, config=None):

    """

    Performs vanilla stochastic gradient descent.

    config format:

    - learning_rate: Scalar learning rate.

    """

    if config is None: config = {}

    config.setdefault('learning_rate', 1e-2)

    w -= config['learning_rate'] * dw    

    return w, config

'''

SGD:随机梯度下降：由梯度计算新的权重矩阵w

sgd_momentum 是sgd的改进版，解决sgd更新不稳定，陷入局部最优的问题。

增加一个动量因子momentum，可以在一定程度上增加稳定性，

从而学习地更快，并且还有一定摆脱局部最优的能力。

'''

def sgd_momentum(w, dw, config=None):

    """

    Performs stochastic gradient descent with momentum.

    config format:

    - learning_rate: Scalar learning rate.

    - momentum: Scalar between 0 and 1 giving the momentum value.

    Setting momentum = 0 reduces to sgd.

    - velocity（速度）: A numpy array of the same shape as w and dw used to store a moving

    average of the gradients.

    """

    if config is None: config = {}

    config.setdefault('learning_rate', 1e-2)

    config.setdefault('momentum', 0.9)

    # config 如果存在属性velocity，则获取config['velocity']，否则获取np.zeros_like(w)

    v = config.get('velocity', np.zeros_like(w))

    next_w = None

    v = config['momentum'] * v - config['learning_rate'] * dw

    next_w = w + v

    config['velocity'] = v    

    return next_w, config

def rmsprop(x, dx, config=None):

    """

    Uses the RMSProp update rule, which uses a moving average of squared gradient

    values to set adaptive per-parameter learning rates.

    config format:

    - learning_rate: Scalar learning rate.

    - decay_rate: Scalar between 0 and 1 giving the decay rate for the squared

    gradient cache.

    - epsilon: Small scalar used for smoothing to avoid dividing by zero.

    - cache: Moving average of second moments of gradients.

    """

    if config is None: config = {}

    config.setdefault('learning_rate', 1e-2)

    config.setdefault('decay_rate', 0.99)

    config.setdefault('epsilon', 1e-8)

    config.setdefault('cache', np.zeros_like(x))

    next_x = None

    cache = config['cache']

    decay_rate = config['decay_rate']

    learning_rate = config['learning_rate']

    epsilon = config['epsilon']

    cache = decay_rate * cache + (1 - decay_rate) * (dx**2)

    x += - learning_rate * dx / (np.sqrt(cache) + epsilon)

    config['cache'] = cache

    next_x = x    

    return next_x, config

def adam(x, dx, config=None):

    """

    Uses the Adam update rule, which incorporates moving averages of both the

    gradient and its square and a bias correction term.

    config format:

    - learning_rate: Scalar learning rate.

    - beta1: Decay rate for moving average of first moment of gradient.

    - beta2: Decay rate for moving average of second moment of gradient.

    - epsilon: Small scalar used for smoothing to avoid dividing by zero.

    - m: Moving average of gradient.

    - v: Moving average of squared gradient.

    - t: Iteration number.

    """

    if config is None: config = {}

    config.setdefault('learning_rate', 1e-3)

    config.setdefault('beta1', 0.9)

    config.setdefault('beta2', 0.999)

    config.setdefault('epsilon', 1e-8)

    config.setdefault('m', np.zeros_like(x))

    config.setdefault('v', np.zeros_like(x))

    config.setdefault('t', 0)

    next_x = None

    m = config['m']

    v = config['v']

    beta1 = config['beta1']

    beta2 = config['beta2']

    learning_rate = config['learning_rate']

    epsilon = config['epsilon']

    t = config['t']

    t += 1

    m = beta1 * m + (1 - beta1) * dx

    v = beta2 * v + (1 - beta2) * (dx**2)

    m_bias = m / (1 - beta1**t)

    v_bias = v / (1 - beta2**t)

    x += - learning_rate * m_bias / (np.sqrt(v_bias) + epsilon)

    next_x = x

    config['m'] = m

    config['v'] = v

    config['t'] = t    

    return next_x, config

import numpy as np

try:

  from . import optim

except Exception:

  import optim

class Solver(object):

  """

  A Solver encapsulates all the logic necessary for training classification

  models. The Solver performs stochastic gradient descent using different

  update rules defined in optim.py.

  The solver accepts both training and validataion data and labels so it can

  periodically check classification accuracy on both training and validation

  data to watch out for overfitting.

  To train a model, you will first construct a Solver instance, passing the

  model, dataset, and various optoins (learning rate, batch size, etc) to the

  constructor. You will then call the train() method to run the optimization

  procedure and train the model.

  After the train() method returns, model.params will contain the parameters

  that performed best on the validation set over the course of training.

  In addition, the instance variable solver.loss_history will contain a list

  of all losses encountered during training and the instance variables

  solver.train_acc_history and solver.val_acc_history will be lists containing

  the accuracies of the model on the training and validation set at each epoch.

  Example usage might look something like this:

  data = {

    'X_train': # training data

    'y_train': # training labels

    'X_val': # validation data

    'X_train': # validation labels

  }

  model = MyAwesomeModel(hidden_size=100, reg=10)

  solver = Solver(model, data,

                  update_rule='sgd',

                  optim_config={

                    'learning_rate': 1e-3,

                  },

                  lr_decay=0.95,

                  num_epochs=10, batch_size=100,

                  print_every=100)

  solver.train()

  A Solver works on a model object that must conform to the following API:

  - model.params must be a dictionary mapping string parameter names to numpy

    arrays containing parameter values.

  - model.loss(X, y) must be a function that computes training-time loss and

    gradients, and test-time classification scores, with the following inputs

    and outputs:

    Inputs:

    - X: Array giving a minibatch of input data of shape (N, d_1, ..., d_k)

    - y: Array of labels, of shape (N,) giving labels for X where y[i] is the

      label for X[i].

    Returns:

    If y is None, run a test-time forward pass and return:

    - scores: Array of shape (N, C) giving classification scores for X where

      scores[i, c] gives the score of class c for X[i].

    If y is not None, run a training time forward and backward pass and return

    a tuple of:

    - loss: Scalar giving the loss

    - grads: Dictionary with the same keys as self.params mapping parameter

      names to gradients of the loss with respect to those parameters.

  """

  def __init__(self, model, data, **kwargs):

    """

    Construct a new Solver instance.

    Required arguments:

    - model: A model object conforming to the API described above

    - data: A dictionary of training and validation data with the following:

      'X_train': Array of shape (N_train, d_1, ..., d_k) giving training images

      'X_val': Array of shape (N_val, d_1, ..., d_k) giving validation images

      'y_train': Array of shape (N_train,) giving labels for training images

      'y_val': Array of shape (N_val,) giving labels for validation images

    Optional arguments:

    - update_rule: A string giving the name of an update rule in optim.py.

      Default is 'sgd'.

    - optim_config: A dictionary containing hyperparameters that will be

      passed to the chosen update rule. Each update rule requires different

      hyperparameters (see optim.py) but all update rules require a

      'learning_rate' parameter so that should always be present.

    - lr_decay: A scalar for learning rate decay; after each epoch the learning

      rate is multiplied by this value.

    - batch_size: Size of minibatches used to compute loss and gradient during

      training.

    - num_epochs: The number of epochs to run for during training.

    - print_every: Integer; training losses will be printed every print_every

      iterations.

    - verbose: Boolean; if set to false then no output will be printed during

      training.

    """

    self.model = model

    self.X_train = data['X_train']

    self.y_train = data['y_train']

    self.X_val = data['X_val']

    self.y_val = data['y_val']

    # Unpack keyword arguments

    # pop(key, default):删除kwargs对象中key，如果存在该key，返回该key对应的value，否则，返回default值。

    self.update_rule = kwargs.pop('update_rule', 'sgd')

    self.optim_config = kwargs.pop('optim_config', {})

    self.lr_decay = kwargs.pop('lr_decay', 1.0)

    self.batch_size = kwargs.pop('batch_size', 2)

    self.num_epochs = kwargs.pop('num_epochs', 10)

    self.print_every = kwargs.pop('print_every', 10)

    self.verbose = kwargs.pop('verbose', True)

    # Throw an error if there are extra keyword arguments

    # 删除kwargs中参数后，校验是否还有多余参数

    if len(kwargs) > 0:

      extra = ', '.join('"%s"' % k for k in kwargs.keys())

      raise ValueError('Unrecognized arguments %s' % extra)

    # Make sure the update rule exists, then replace the string

    # name with the actual function

    # 检查optim对象中是否有属性或方法名为self.update_rule

    if not hasattr(optim, self.update_rule):

      raise ValueError('Invalid update_rule "%s"' % self.update_rule)

    self.update_rule = getattr(optim, self.update_rule)

    self._reset()

  def _reset(self):

    """

    Set up some book-keeping variables for optimization. Don't call this

    manually.

    """

    # Set up some variables for book-keeping

    self.epoch = 0

    self.best_val_acc = 0

    self.best_params = {}

    self.loss_history = []

    self.train_acc_history = []

    self.val_acc_history = []

    # Make a deep copy of the optim_config for each parameter

    self.optim_configs = {}

    for p in self.model.params:

      d = {k: v for k, v in self.optim_config.items()}

      self.optim_configs[p] = d

  def _step(self):

    """

    Make a single gradient update. This is called by train() and should not

    be called manually.

    """

    # Make a minibatch of training data

    # 500 张图片

    num_train = self.X_train.shape[0]

    # 随机选出batch_size：2 张

    batch_mask = np.random.choice(num_train, self.batch_size)

   # batch_mask = [t%(num_train//2), num_train//2 + t%(num_train//2)]

    # 训练样本矩阵[2,3,32,32]

    X_batch = self.X_train[batch_mask]

    # 标签矩阵[2,] 图片类型

    y_batch = self.y_train[batch_mask]

    # Compute loss and gradient

    loss, grads = self.model.loss(X_batch, y_batch)

    self.loss_history.append(loss)

    # 更新模型超参(w1,b1),(w2,b2),(w3,b3)，以及保存更新超参时对应参数因子

    # Perform a parameter update

    for p, w in self.model.params.items():

      dw = grads[p]

      config = self.optim_configs[p]

      next_w, next_config = self.update_rule(w, dw, config)

      self.model.params[p] = next_w

      # 保存参数因子，learning_rate(学习率)，velocity(速度)

      self.optim_configs[p] = next_config

  def check_accuracy(self, X, y, num_samples=None, batch_size=2):

    """

    Check accuracy of the model on the provided data.

    Inputs:

    - X: Array of data, of shape (N, d_1, ..., d_k)

    - y: Array of labels, of shape (N,)

    - num_samples: If not None, subsample the data and only test the model

      on num_samples datapoints.

    - batch_size: Split X and y into batches of this size to avoid using too

      much memory.

    Returns:

    - acc: Scalar giving the fraction of instances that were correctly

      classified by the model.

    """

    # Maybe subsample the data

    N = X.shape[0]

    if num_samples is not None and N > num_samples:

      # 随机选取num_samples张图片，返回选取图片索引

      mask = np.random.choice(N, num_samples)

      N = num_samples

      X = X[mask]

      y = y[mask]

    # Compute predictions in batches

    num_batches = N // batch_size

    if N % batch_size != 0:

      num_batches += 1

    y_pred = []

    for i in range(num_batches):

      start = i * batch_size

      end = (i + 1) * batch_size

      scores = self.model.loss(X[start:end])

      y_pred.append(np.argmax(scores, axis=1))

    y_pred = np.hstack(y_pred)

    acc = np.mean(y_pred == y)

    return acc

  '''

   训练模型：核心方法

   epoch > batch_size > iteration >= 1

   训练总的次数 = num_epochs * iterations_per_epoch

  '''

  def train(self):

    """

    Run optimization to train the model.

    """

    num_train = self.X_train.shape[0]

    iterations_per_epoch = max(num_train // self.batch_size, 1)

    num_iterations = self.num_epochs * iterations_per_epoch

    # 迭代总的次数

    for t in range(num_iterations):

      # 某次iteration训练

      self._step()

      # Maybe print training loss

      # verbose：是否显示详细信息

      if self.verbose and t % self.print_every == 0:

        print ('(Iteration %d / %d) loss: %f' % (

               t + 1, num_iterations, self.loss_history[-1]))

      # At the end of every epoch, increment the epoch counter and decay the

      # learning rate.

      # 每迭代完一次epoch后，更新学习率learning_rate，加快运算效率。

      epoch_end = (t + 1) % iterations_per_epoch == 0

      if epoch_end:

        self.epoch += 1

        for k in self.optim_configs:

          self.optim_configs[k]['learning_rate'] *= self.lr_decay

      # Check train and val accuracy on the first iteration, the last

      # iteration, and at the end of each epoch.

      # 在第1次迭代，最后1次迭代，或者运行完一个epoch后，校验训练结果。

      first_it = (t == 0)

      last_it = (t == num_iterations + 1)

      if first_it or last_it or epoch_end:

        train_acc = self.check_accuracy(self.X_train, self.y_train,

                                        num_samples=4)

        val_acc = self.check_accuracy(self.X_val, self.y_val,num_samples=4)

        self.train_acc_history.append(train_acc)

        self.val_acc_history.append(val_acc)

        if self.verbose:

          print ('(Epoch %d / %d) train acc: %f; val_acc: %f' % (

                 self.epoch, self.num_epochs, train_acc, val_acc))

        # Keep track of the best model

        if val_acc > self.best_val_acc:

          self.best_val_acc = val_acc

          self.best_params = {}

          for k, v in self.model.params.items():

            self.best_params[k] = v.copy()

    # At the end of training swap the best params into the model

    self.model.params = self.best_params