Sequential Recommendations

z_t = σ(W_z [h_{t-1}, x_t] + b_z)         # Update gate
r_t = σ(W_r [h_{t-1}, x_t] + b_r)         # Reset gate
h̃_t = tanh(W [r_t ⊙ h_{t-1}, x_t] + b)   # Candidate
h_t = (1 - z_t) ⊙ h_{t-1} + z_t ⊙ h̃_t    # New hidden state

BPR-max Loss:
  s_pos = score(h_t, i_{t+1})           # Score of true next item
  s_neg = max over all negative items   # Worst negative sample
  L = -log(σ(s_pos - s_neg))            # σ is sigmoid

  Intuition: Maximize margin between positive and hardest negative.
  The "max" focuses on the hardest negatives to beat.

Algorithm: GRU4Rec Training

For each epoch:
  For each mini-batch of sessions B:
    1. Pad sessions in B to max length in B
    2. Initialize GRU hidden state h_0 = 0

    For each timestep t in max_length:
      3. Embed items at position t: X_t = Embed(items[t])
      4. Forward GRU: h_t = GRU(X_t, h_{t-1})
      5. Score all items: logits = W @ h_t + b
      6. Identify true next items (labels)
      7. Sample negatives for each session
      8. Compute BPR-max loss
      9. Backward pass (BPTT)
      10. Update params (Adam)

    11. Update h_0 = h_T for next batch (reset per session)

Attention Mask (T=4):
[1, 0, 0, 0]      # Position 1 attends only to itself
[1, 1, 0, 0]      # Position 2 attends to 1, 2
[1, 1, 1, 0]      # Position 3 attends to 1, 2, 3
[1, 1, 1, 1]      # Position 4 attends to 1, 2, 3, 4

Set masked positions to -∞ before softmax, they become ~0 after.

Causal LM Loss for next-item prediction:
  L = Σ_t cross_entropy(logits_t, i_{t+1})

  At position t, predict next item i_{t+1} from context [i_1...i_t].
  Compute loss only on non-padded positions.
  Softmax over all items (or sampled softmax for large vocabularies).

BERT4Rec Training Algorithm:

For each training sequence [i_1, i_2, i_3, i_4]:
  1. Randomly select 15% of positions (e.g., position 3)
  2. Replace with special [MASK] token
  3. Corrupted sequence: [i_1, i_2, [MASK], i_4]
  4. Feed to bidirectional Transformer
  5. Predict: position 3 → should be i_3
  6. Loss = cross_entropy(logits_3, i_3)
  7. Backprop and update

Repeat for multiple epochs with different masking.

At inference (next-item prediction):
  - Can't use [MASK] since we don't know the next item yet!
  - Use last hidden state directly, or fine-tune with causal mask
  - Some implementations retrain decoder with causal masking

Time Gap Encoding:
  gap_t = t_i - t_{i-1}  # seconds, minutes, or days

  Option 1: Sinusoidal (from Transformer)
    pos_enc(gap_t) = [sin(gap_t/10000^0), cos(...), sin(...), ...]

  Option 2: Learned embedding
    time_emb = Embedding(quantize(gap_t))  # e.g., buckets: [0, 1h), [1h, 1d), etc.

  Concatenate with item embedding to form augmented feature.
  Helps model distinguish between rapid clicks vs long waits.

import numpy as np
import pandas as pd
from collections import defaultdict

# Generate synthetic sessions
np.random.seed(42)
num_sessions = 500
num_items = 100
max_seq_len = 10

sessions = []
for s_id in range(num_sessions):
    # Random session length
    seq_len = np.random.randint(2, max_seq_len + 1)
    # Sample items without replacement
    seq = np.random.choice(num_items, seq_len, replace=False).tolist()
    sessions.append(seq)

print(f"Sessions: {len(sessions)}, Items: {num_items}")
print(f"Example session: {sessions[0]}")

# Split: 80% train, 20% test
train_sessions = sessions[:400]
test_sessions = sessions[400:]

print(f"Train: {len(train_sessions)}, Test: {len(test_sessions)}")

class GRU4Rec:
    def __init__(self, num_items, embedding_dim=32, hidden_dim=64, lr=0.01):
        self.num_items = num_items
        self.embedding_dim = embedding_dim
        self.hidden_dim = hidden_dim
        self.lr = lr

        # Initialize embeddings and weights
        self.item_embed = np.random.randn(num_items, embedding_dim) * 0.01
        self.W_z = np.random.randn(embedding_dim + hidden_dim, hidden_dim) * 0.01  # Update gate
        self.W_r = np.random.randn(embedding_dim + hidden_dim, hidden_dim) * 0.01  # Reset gate
        self.W = np.random.randn(embedding_dim + hidden_dim, hidden_dim) * 0.01    # Candidate
        self.W_out = np.random.randn(hidden_dim, num_items) * 0.01                 # Output
        self.b_z = np.zeros(hidden_dim)
        self.b_r = np.zeros(hidden_dim)
        self.b = np.zeros(hidden_dim)
        self.b_out = np.zeros(num_items)

    def sigmoid(self, x):
        return 1 / (1 + np.exp(-np.clip(x, -500, 500)))

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

    def gru_forward(self, x_t, h_prev):
        """Single GRU step: x_t (embedding), h_prev (hidden state)"""
        combined = np.concatenate([h_prev, x_t])

        z_t = self.sigmoid(combined @ self.W_z + self.b_z)      # Update gate
        r_t = self.sigmoid(combined @ self.W_r + self.b_r)      # Reset gate
        h_tilde = self.tanh(np.concatenate([r_t * h_prev, x_t]) @ self.W + self.b)
        h_t = (1 - z_t) * h_prev + z_t * h_tilde
        return h_t, z_t, r_t, h_tilde

    def forward(self, session):
        """Forward pass for a single session"""
        h = np.zeros(self.hidden_dim)
        h_list = [h]

        for item_id in session:
            x_t = self.item_embed[item_id]
            h, _, _, _ = self.gru_forward(x_t, h)
            h_list.append(h)

        # Output at final step
        logits = h @ self.W_out + self.b_out
        return logits, h, h_list

    def train_step(self, session):
        """Train on one session (simplified: ignore mask for now)"""
        if len(session) < 2:
            return 0

        # Forward pass
        logits, h_final, h_list = self.forward(session[:-1])

        # Compute ranking loss (simplified BPR-max)
        true_item = session[-1]
        pos_score = logits[true_item]

        # Sample negatives
        neg_items = np.random.choice([i for i in range(self.num_items) if i != true_item], 5)
        neg_scores = logits[neg_items]
        max_neg = np.max(neg_scores)

        # BPR loss (simplified): -log(sigmoid(pos - max_neg))
        loss = -np.log(self.sigmoid(pos_score - max_neg) + 1e-10)

        # Backward pass (simplified gradient update)
        grad_logits = np.zeros(self.num_items)
        grad_logits[true_item] = -1 / (self.sigmoid(pos_score - max_neg) + 1e-10)
        grad_logits[neg_items] = 1 / (self.sigmoid(pos_score - max_neg) + 1e-10) * (1 / len(neg_items))

        grad_h = grad_logits @ self.W_out.T
        self.W_out -= self.lr * np.outer(h_final, grad_logits)
        self.b_out -= self.lr * grad_logits

        return loss

    def evaluate(self, test_sessions, k=10):
        """Evaluate HR@K"""
        hits = 0
        for session in test_sessions:
            if len(session) < 2:
                continue
            logits, _, _ = self.forward(session[:-1])
            top_k = np.argsort(-logits)[:k]
            if session[-1] in top_k:
                hits += 1

        hr = hits / len(test_sessions) if test_sessions else 0
        return hr

# Training loop
model = GRU4Rec(num_items=num_items, embedding_dim=32, hidden_dim=64)
for epoch in range(10):
    total_loss = 0
    for session in train_sessions:
        loss = model.train_step(session)
        total_loss += loss

    hr = model.evaluate(test_sessions, k=10)
    print(f"Epoch {epoch+1}: Loss={total_loss/len(train_sessions):.4f}, HR@10={hr:.4f}")

class SimpleAttention:
    def __init__(self, d_model=32, num_heads=2, dropout=0.1):
        self.d_model = d_model
        self.num_heads = num_heads
        self.head_dim = d_model // num_heads
        self.dropout = dropout

        self.W_q = np.random.randn(d_model, d_model) * 0.01
        self.W_k = np.random.randn(d_model, d_model) * 0.01
        self.W_v = np.random.randn(d_model, d_model) * 0.01
        self.W_o = np.random.randn(d_model, d_model) * 0.01

    def scaled_dot_product_attention(self, Q, K, V, mask=None):
        """
        Q, K, V: (seq_len, d_model)
        mask: (seq_len, seq_len) causal mask
        """
        scores = (Q @ K.T) / np.sqrt(self.head_dim)

        if mask is not None:
            scores[mask == 0] = -1e9

        attn = self.softmax(scores)
        out = attn @ V
        return out, attn

    def softmax(self, 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 forward(self, X, mask=None):
        """
        X: (seq_len, d_model) - sequence of embeddings
        mask: (seq_len, seq_len) - causal mask (lower triangular)
        """
        Q = X @ self.W_q
        K = X @ self.W_k
        V = X @ self.W_v

        attn_out, attn_weights = self.scaled_dot_product_attention(Q, K, V, mask)
        output = attn_out @ self.W_o
        return output, attn_weights


class SASRecSimplified:
    def __init__(self, num_items, d_model=32, num_heads=2, lr=0.01):
        self.num_items = num_items
        self.d_model = d_model
        self.num_heads = num_heads
        self.lr = lr

        self.item_embed = np.random.randn(num_items, d_model) * 0.01
        self.pos_embed = np.random.randn(100, d_model) * 0.01  # Max seq len
        self.attention = SimpleAttention(d_model, num_heads)
        self.W_out = np.random.randn(d_model, num_items) * 0.01
        self.b_out = np.zeros(num_items)

    def forward(self, session):
        """Forward pass with attention"""
        seq_len = len(session)

        # Embed and add positional encoding
        X = np.zeros((seq_len, self.d_model))
        for i, item_id in enumerate(session):
            X[i] = self.item_embed[item_id] + self.pos_embed[i]

        # Causal mask
        mask = np.tril(np.ones((seq_len, seq_len)))

        # Attention
        attn_out, _ = self.attention.forward(X, mask)

        # Output at last position
        h_final = attn_out[-1]
        logits = h_final @ self.W_out + self.b_out
        return logits, attn_out

    def evaluate(self, test_sessions, k=10):
        """Evaluate HR@K"""
        hits = 0
        for session in test_sessions:
            if len(session) < 2:
                continue
            logits, _ = self.forward(session[:-1])
            top_k = np.argsort(-logits)[:k]
            if session[-1] in top_k:
                hits += 1

        hr = hits / len(test_sessions) if test_sessions else 0
        return hr

# Quick eval
sasrec = SASRecSimplified(num_items=num_items, d_model=32)
hr_sasrec = sasrec.evaluate(test_sessions, k=10)
print(f"SASRec HR@10: {hr_sasrec:.4f}")

print("\n=== Model Comparison ===")
print(f"GRU4Rec HR@10:    {model.evaluate(test_sessions, k=10):.4f}")
print(f"SASRec HR@10:     {sasrec.evaluate(test_sessions, k=10):.4f}")

# Timing
import time

start = time.time()
for _ in range(100):
    gru_logits, _, _ = model.forward(test_sessions[0][:-1])
gru_time = (time.time() - start) / 100 * 1000

start = time.time()
for _ in range(100):
    sasrec_logits, _ = sasrec.forward(test_sessions[0][:-1])
sasrec_time = (time.time() - start) / 100 * 1000

print(f"\nInference Time (ms):")
print(f"GRU4Rec:  {gru_time:.2f}ms")
print(f"SASRec:   {sasrec_time:.2f}ms")
print(f"Ratio (SASRec/GRU4Rec): {sasrec_time/gru_time:.2f}x")