10. Deep Learning

import numpy as np

def dense_forward(x, W, b):
    y_linear = np.dot(W, x) + b
    y = np.maximum(0, y_linear)  # ReLU
    return y, y_linear  # Cache linear for backprop

def dense_backward(dy_post_act, x, W, y_linear):
    # dy_post_act: ∂L/∂y (post-ReLU)
    dy_linear = dy_post_act * (y_linear > 0)  # ReLU derivative
    dx = np.dot(W.T, dy_linear)
    dW = np.outer(dy_linear, x)
    db = dy_linear
    return dx, dW, db

# Example
x = np.array([2, 3])
W = np.array([[1, 2], [0, -1]])
b = np.array([1, -1])
y, y_linear = dense_forward(x, W, b)
dy_post_act = np.array([0.5, -0.2])
dx, dW, db = dense_backward(dy_post_act, x, W, y_linear)
print("Forward y:", y)  # [9, 0]
print("dx:", dx)  # [0.5, 1.0]
print("dW:", dW)  # [[1, 1.5], [0, 0]]
print("db:", db)  # [0.5, 0]

import numpy as np
from scipy.signal import correlate2d, convolve2d

def conv_forward(X, K, b):
    Y = correlate2d(X, K, mode='valid') + b  # SciPy correlate for conv
    return Y, X  # Cache X

def conv_backward(dY, X, K):
    # Rotate kernel 180 degrees for full conv
    K_rot = np.rot90(K, 2)
    # Pad dY to match X shape for dx
    pad_h, pad_w = K.shape[0]-1, K.shape[1]-1
    dY_padded = np.pad(dY, ((pad_h//2, pad_h-pad_h//2), (pad_w//2, pad_w-pad_w//2)))
    dX = convolve2d(dY_padded, K_rot, mode='valid')
    dK = correlate2d(X, dY, mode='valid')
    db = np.sum(dY)
    return dX, dK, db

# Example
X = np.array([[1,2,3],[4,5,6],[7,8,9]])
K = np.array([[1,0],[-1,1]])
b = 1
Y, _ = conv_forward(X, K, b)
dY = np.array([[0.5, -0.5],[1, 0]])
dX, dK, db = conv_backward(dY, X, K)
print("Forward Y:\n", Y)
print("dX:\n", dX)
print("dK:\n", dK)
print("db:", db)

import numpy as np

def max_pool_forward(X, pool_size=2, stride=2):
    H, W = X.shape
    out_H, out_W = H // stride, W // stride
    Y = np.zeros((out_H, out_W))
    max_idx = np.zeros_like(X, dtype=bool)  # For backprop
    for i in range(0, H, stride):
        for j in range(0, W, stride):
            slice = X[i:i+pool_size, j:j+pool_size]
            max_val = np.max(slice)
            Y[i//stride, j//stride] = max_val
            max_idx[i:i+pool_size, j:j+pool_size] = (slice == max_val)
    return Y, max_idx

def max_pool_backward(dY, max_idx, pool_size=2, stride=2):
    dX = np.zeros_like(max_idx, dtype=float)
    for i in range(dY.shape[0]):
        for j in range(dY.shape[1]):
            dX[i*stride:i*stride+pool_size, j*stride:j*stride+pool_size] = dY[i,j] * max_idx[i*stride:i*stride+pool_size, j*stride:j*stride+pool_size]
    return dX

# Example
X = np.arange(1,17).reshape(4,4)
Y, max_idx = max_pool_forward(X)
dY = np.array([[0.5, -0.5],[1, 0]])
dX = max_pool_backward(dY, max_idx)
print("Forward Y:\n", Y)
print("dX:\n", dX)

import numpy as np

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

def dsigmoid(y):
    return y * (1 - y)

def tanh(x):
    return np.tanh(x)

def dtanh(y):
    return 1 - y**2

# Forward pass
def lstm_forward(x_t, h_prev, C_prev, W_f, W_i, W_C, W_o, b_f, b_i, b_C, b_o):
    concat = np.concatenate((h_prev, x_t), axis=0)
    f_t = sigmoid(np.dot(W_f, concat) + b_f)
    i_t = sigmoid(np.dot(W_i, concat) + b_i)
    C_tilde = tanh(np.dot(W_C, concat) + b_C)
    C_t = f_t * C_prev + i_t * C_tilde
    o_t = sigmoid(np.dot(W_o, concat) + b_o)
    h_t = o_t * tanh(C_t)
    cache = (concat, f_t, i_t, C_tilde, o_t, C_t)
    return h_t, C_t, cache

# Backward pass
def lstm_backward(dh_next, dC_next, cache, W_f, W_i, W_C, W_o):
    concat, f_t, i_t, C_tilde, o_t, C_t = cache

    # Derivatives
    dC_t = dh_next * o_t * dtanh(tanh(C_t)) + dC_next
    do_t = dh_next * tanh(C_t) * dsigmoid(o_t)
    dC_tilde = dC_t * i_t * dtanh(C_tilde)
    di_t = dC_t * C_tilde * dsigmoid(i_t)
    df_t = dC_t * C_prev * dsigmoid(f_t)
    dC_prev = dC_t * f_t

    # Gradients for gates
    dconcat_o = np.dot(W_o.T, do_t)
    dconcat_C = np.dot(W_C.T, dC_tilde)
    dconcat_i = np.dot(W_i.T, di_t)
    dconcat_f = np.dot(W_f.T, df_t)
    dconcat = dconcat_f + dconcat_i + dconcat_C + dconcat_o

    # Split for h_prev and x_t
    hidden_size = h_prev.shape[0]
    dh_prev = dconcat[:hidden_size]
    dx_t = dconcat[hidden_size:]

    # Parameter gradients
    dW_f = np.outer(df_t, concat)
    db_f = df_t
    dW_i = np.outer(di_t, concat)
    db_i = di_t
    dW_C = np.outer(dC_tilde, concat)
    db_C = dC_tilde
    dW_o = np.outer(do_t, concat)
    db_o = do_t

    return dx_t, dh_prev, dC_prev, dW_f, db_f, dW_i, db_i, dW_C, db_C, dW_o, db_o

# Numerical example (hidden size = 1)
x_t = np.array([0.5])
h_prev = np.array([0.1])
C_prev = np.array([0.2])
W_f = np.array([[0.5, 0.5]])
W_i = np.array([[0.4, 0.4]])
W_C = np.array([[0.3, 0.3]])
W_o = np.array([[0.2, 0.2]])
b_f = np.array([0.0])
b_i = np.array([0.0])
b_C = np.array([0.0])
b_o = np.array([0.0])

# Forward
h_t, C_t, cache = lstm_forward(x_t, h_prev, C_prev, W_f, W_i, W_C, W_o, b_f, b_i, b_C, b_o)
print("Forward h_t:", h_t)  # Output: [0.11199714]
print("Forward C_t:", C_t)  # Output: [0.2145628]

# Backward example: assume dh_next = [0.1], dC_next = [0.05]
dh_next = np.array([0.1])
dC_next = np.array([0.05])
dx_t, dh_prev, dC_prev, dW_f, db_f, dW_i, db_i, dW_C, db_C, dW_o, db_o = lstm_backward(dh_next, dC_next, cache, W_f, W_i, W_C, W_o)

print("Backward dx_t:", dx_t)  # Output: [0.02164056]
print("Backward dh_prev:", dh_prev)  # Output: [0.02164056]
print("Backward dC_prev:", dC_prev)  # Output: [0.05780591]
print("Backward dW_f:", dW_f)  # Output: [[0.00049199 0.00245997]]
print("Backward db_f:", db_f)  # Output: [0.00491995]
print("Backward dW_i:", dW_i)  # Output: [[0.00044162 0.00220808]]
print("Backward db_i:", db_i)  # Output: [0.00441615]
print("Backward dW_C:", dW_C)  # Output: [[0.00545376 0.02726878]]
print("Backward db_C:", db_C)  # Output: [0.05453756]
print("Backward dW_o:", dW_o)  # Output: [[0.00052643 0.00263213]]
print("Backward db_o:", db_o)  # Output: [0.00526427]

import numpy as np

def embedding_forward(index, E):
    return E[index]

def embedding_backward(dy, index, E_shape):
    dE = np.zeros(E_shape)
    dE[index] = dy
    return dE

# Example
E = np.array([[0.1,0.2,0.3],[0.4,0.5,0.6]])
index = 1
y = embedding_forward(index, E)
dy = np.array([0.1, -0.1, 0.2])
dE = embedding_backward(dy, index, E.shape)
print("dE:\n", dE)

import numpy as np

def softmax(x):
    exp_x = np.exp(x - np.max(x, axis=-1, keepdims=True))
    return exp_x / np.sum(exp_x, axis=-1, keepdims=True)

def attention_forward(Q, K, V):
    d = Q.shape[-1]
    scores = np.dot(Q, K.T) / np.sqrt(d)
    weights = softmax(scores)
    attn = np.dot(weights, V)
    return attn, (scores, weights, K, V)  # Cache

def attention_backward(dattn, cache):
    scores, weights, K, V = cache
    dweights = np.dot(dattn, V.T)
    dscores = weights * (dweights - np.sum(weights * dweights, axis=-1, keepdims=True))
    dQ = np.dot(dscores, K) / np.sqrt(K.shape[-1])
    dK = np.dot(dscores.T, Q) / np.sqrt(K.shape[-1])
    dV = np.dot(weights.T, dattn)
    return dQ, dK, dV

# Example
Q = K = V = np.array([[1.,0.],[0.,1.]])
attn, cache = attention_forward(Q, K, V)
dattn = np.array([[0.1,0.2],[ -0.1,0.3]])
dQ, dK, dV = attention_backward(dattn, cache)
print("dQ:\n", dQ)

import numpy as np

def batch_norm_forward(x, gamma, beta, epsilon=1e-4):
    mu = np.mean(x)
    var = np.var(x)
    x_hat = (x - mu) / np.sqrt(var + epsilon)
    y = gamma * x_hat + beta
    return y, (x_hat, mu, var)

def batch_norm_backward(dy, cache, gamma):
    x_hat, mu, var = cache
    N = dy.shape[0]
    dx_hat = dy * gamma
    dvar = np.sum(dx_hat * (x - mu) * -0.5 * (var + epsilon)**(-1.5), axis=0)
    dmu = np.sum(dx_hat * -1 / np.sqrt(var + epsilon), axis=0) + dvar * np.mean(-2 * (x - mu), axis=0)
    dx = dx_hat / np.sqrt(var + epsilon) + dvar * 2 * (x - mu) / N + dmu / N
    dgamma = np.sum(dy * x_hat, axis=0)
    dbeta = np.sum(dy, axis=0)
    return dx, dgamma, dbeta

# Example
x = np.array([1,2,3,4.])
gamma, beta = 1, 0
y, cache = batch_norm_forward(x, gamma, beta)
dy = np.array([0.1,0.2,-0.1,0.3])
dx, dgamma, dbeta = batch_norm_backward(dy, cache, gamma)
print("dx:", dx)
print("dgamma:", dgamma)
print("dbeta:", dbeta)

import numpy as np

def dropout_forward(x, p, training=True):
    if training:
        mask = np.random.binomial(1, 1-p, size=x.shape) / (1-p)
        y = x * mask
        return y, mask
    return x, None

def dropout_backward(dy, mask):
    if mask is None:
        return dy
    return dy * mask

# Example
np.random.seed(0)
x = np.array([1,2,3,4.])
p = 0.5
y, mask = dropout_forward(x, p)
dy = np.array([0.1,0.2,0.3,0.4])
dx = dropout_backward(dy, mask)
print("dx:", dx)

import numpy as np

def flatten_forward(x):
    return x.flatten(), x.shape

def flatten_backward(dy, orig_shape):
    return dy.reshape(orig_shape)

# Example
x = np.array([[1,2],[3,4]])
y, shape = flatten_forward(x)
dy = np.array([0.1,0.2,0.3,0.4])
dx = flatten_backward(dy, shape)
print("dx:\n", dx)

import numpy as np

def relu_forward(x):
    return np.maximum(0, x), x

def relu_backward(dy, x_cache):
    return dy * (x_cache > 0)

# Example
x = np.array([-1,0,2,-3])
y, x_cache = relu_forward(x)
dy = np.array([0.5,-0.5,1,0])
dx = relu_backward(dy, x_cache)
print("dx:", dx)