Key Code Examples
1. Neural Network from Scratch (NumPy)
import numpy as np
class NeuralNetwork:
"""Simple 2-layer neural network with backpropagation."""
def __init__(self, input_size, hidden_size, output_size):
# Initialize weights with Xavier initialization
self.W1 = np.random.randn(input_size, hidden_size) * np.sqrt(2.0 / input_size)
self.b1 = np.zeros((1, hidden_size))
self.W2 = np.random.randn(hidden_size, output_size) * np.sqrt(2.0 / hidden_size)
self.b2 = np.zeros((1, output_size))
def sigmoid(self, z):
return 1 / (1 + np.exp(-np.clip(z, -500, 500)))
def sigmoid_derivative(self, z):
s = self.sigmoid(z)
return s * (1 - s)
def forward(self, X):
self.z1 = X @ self.W1 + self.b1
self.a1 = self.sigmoid(self.z1)
self.z2 = self.a1 @ self.W2 + self.b2
self.a2 = self.sigmoid(self.z2)
return self.a2
def backward(self, X, y, learning_rate):
m = X.shape[0]
# Output layer gradients
dz2 = self.a2 - y
dW2 = (self.a1.T @ dz2) / m
db2 = np.sum(dz2, axis=0, keepdims=True) / m
# Hidden layer gradients
dz1 = (dz2 @ self.W2.T) * self.sigmoid_derivative(self.z1)
dW1 = (X.T @ dz1) / m
db1 = np.sum(dz1, axis=0, keepdims=True) / m
# Update weights
self.W1 -= learning_rate * dW1
self.b1 -= learning_rate * db1
self.W2 -= learning_rate * dW2
self.b2 -= learning_rate * db2
def train(self, X, y, epochs=1000, lr=0.1):
for epoch in range(epochs):
output = self.forward(X)
self.backward(X, y, lr)
if epoch % 200 == 0:
loss = -np.mean(y * np.log(output + 1e-8) +
(1-y) * np.log(1-output + 1e-8))
print(f"Epoch {epoch}: loss = {loss:.4f}")
# Example: XOR problem
X = np.array([[0,0], [0,1], [1,0], [1,1]], dtype=float)
y = np.array([[0], [1], [1], [0]], dtype=float)
nn = NeuralNetwork(input_size=2, hidden_size=4, output_size=1)
nn.train(X, y, epochs=2000, lr=0.5)
predictions = nn.forward(X)
print(f"Predictions:\n{predictions.round(3)}")
2. A* Pathfinding Algorithm
import heapq
def astar(grid, start, goal):
"""A* pathfinding on a 2D grid. 0=walkable, 1=obstacle."""
rows, cols = len(grid), len(grid[0])
def heuristic(a, b):
# Manhattan distance
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def get_neighbors(r, c):
directions = [(-1,0), (1,0), (0,-1), (0,1)]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
yield (nr, nc)
open_set = [(heuristic(start, goal), 0, start)]
came_from = {}
g_score = {start: 0}
visited = set()
while open_set:
f, g, current = heapq.heappop(open_set)
if current == goal:
# Reconstruct path
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
if current in visited:
continue
visited.add(current)
for neighbor in get_neighbors(*current):
tentative_g = g_score[current] + 1
if tentative_g < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score, tentative_g, neighbor))
return None # No path found
# Example grid (0=walkable, 1=obstacle)
grid = [
[0, 0, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
]
path = astar(grid, (0, 0), (4, 4))
print(f"Path: {path}")
3. Decision Tree with Information Gain
import numpy as np
from collections import Counter
def entropy(labels):
"""Calculate Shannon entropy: -Σ p(x) log₂ p(x)"""
counts = Counter(labels)
total = len(labels)
return -sum((count/total) * np.log2(count/total)
for count in counts.values())
def information_gain(feature_values, labels):
"""Calculate information gain from splitting on a feature."""
total_entropy = entropy(labels)
values = set(feature_values)
weighted_entropy = 0
for val in values:
subset = [l for f, l in zip(feature_values, labels) if f == val]
weighted_entropy += (len(subset)/len(labels)) * entropy(subset)
return total_entropy - weighted_entropy
# Example: Should we play tennis?
# Feature: Weather (Sunny, Overcast, Rain)
# Label: Play (Yes, No)
weather = ['Sunny','Sunny','Overcast','Rain','Rain','Rain',
'Overcast','Sunny','Sunny','Rain','Sunny','Overcast',
'Overcast','Rain']
play = ['No','No','Yes','Yes','Yes','No',
'Yes','No','Yes','Yes','Yes','Yes',
'Yes','No']
ig = information_gain(weather, play)
print(f"Information Gain (Weather): {ig:.4f}")
# Output: 0.2467
4. Q-Learning (Reinforcement Learning)
import numpy as np
class QLearningAgent:
"""Q-Learning agent for grid-world navigation."""
def __init__(self, n_states, n_actions, alpha=0.1, gamma=0.95, epsilon=0.1):
self.q_table = np.zeros((n_states, n_actions))
self.alpha = alpha # learning rate
self.gamma = gamma # discount factor
self.epsilon = epsilon # exploration rate
def choose_action(self, state):
if np.random.random() < self.epsilon:
return np.random.randint(self.q_table.shape[1]) # Explore
return np.argmax(self.q_table[state]) # Exploit
def update(self, state, action, reward, next_state, done):
best_next = np.max(self.q_table[next_state])
current = self.q_table[state, action]
# Q-learning update rule
self.q_table[state, action] = current + self.alpha * (
reward + self.gamma * best_next - current
)
def train(self, env, episodes=1000):
rewards_history = []
for ep in range(episodes):
state = env.reset()
total_reward = 0
done = False
while not done:
action = self.choose_action(state)
next_state, reward, done = env.step(action)
self.update(state, action, reward, next_state, done)
state = next_state
total_reward += reward
rewards_history.append(total_reward)
# Decay exploration
self.epsilon = max(0.01, self.epsilon * 0.995)
return rewards_history
# Simple grid world example
class SimpleGrid:
"""4x4 grid: start at (0,0), goal at (3,3). Reward +10 goal, -1 step."""
def __init__(self):
self.state = 0 # 0 to 15 (4x4 grid)
self.goal = 15
def reset(self):
self.state = 0
return self.state
def step(self, action):
# Actions: 0=up, 1=down, 2=left, 3=right
row, col = divmod(self.state, 4)
if action == 0: row = max(0, row-1)
elif action == 1: row = min(3, row+1)
elif action == 2: col = max(0, col-1)
elif action == 3: col = min(3, col+1)
self.state = row * 4 + col
reward = 10 if self.state == self.goal else -1
done = self.state == self.goal
return self.state, reward, done
# Train
agent = QLearningAgent(n_states=16, n_actions=4)
env = SimpleGrid()
rewards = agent.train(env, episodes=500)
print(f"Average reward (last 100 episodes): {np.mean(rewards[-100:]):.2f}")
5. CNN for Image Classification (TensorFlow/Keras)
import tensorflow as tf
from tensorflow.keras import layers, models
def build_cnn(input_shape=(28, 28, 1), num_classes=10):
"""Build a Convolutional Neural Network for digit classification."""
model = models.Sequential([
# First conv block
layers.Conv2D(32, (3, 3), activation='relu', input_shape=input_shape),
layers.MaxPooling2D((2, 2)),
# Second conv block
layers.Conv2D(64, (3, 3), activation='relu'),
layers.MaxPooling2D((2, 2)),
# Third conv block
layers.Conv2D(64, (3, 3), activation='relu'),
# Dense classifier
layers.Flatten(),
layers.Dense(64, activation='relu'),
layers.Dropout(0.5),
layers.Dense(num_classes, activation='softmax'),
])
model.compile(
optimizer='adam',
loss='sparse_categorical_crossentropy',
metrics=['accuracy']
)
return model
# Load MNIST data
(X_train, y_train), (X_test, y_test) = tf.keras.datasets.mnist.load_data()
X_train = X_train.reshape(-1, 28, 28, 1).astype('float32') / 255.0
X_test = X_test.reshape(-1, 28, 28, 1).astype('float32') / 255.0
# Build and train
model = build_cnn()
model.fit(X_train, y_train, epochs=5, batch_size=64,
validation_split=0.1, verbose=1)
# Evaluate
test_loss, test_acc = model.evaluate(X_test, y_test)
print(f"Test accuracy: {test_acc:.4f}") # ~0.99
6. Transformer Attention Mechanism
import numpy as np
def scaled_dot_product_attention(Q, K, V, mask=None):
"""Compute attention: Attention(Q,K,V) = softmax(QK^T/√d_k) V"""
d_k = Q.shape[-1]
scores = np.dot(Q, K.T) / np.sqrt(d_k)
if mask is not None:
scores = np.where(mask, scores, -1e9)
# Softmax
exp_scores = np.exp(scores - np.max(scores, axis=-1, keepdims=True))
attention_weights = exp_scores / np.sum(exp_scores, axis=-1, keepdims=True)
output = np.dot(attention_weights, V)
return output, attention_weights
# Example: Self-attention on 3 tokens, each with 4-dim embeddings
Q = np.array([[1, 0, 1, 0], # Token 1 query
[0, 1, 0, 1], # Token 2 query
[1, 1, 0, 0]]) # Token 3 query
K = np.array([[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 1, 0, 0]])
V = np.array([[1, 2],
[3, 4],
[5, 6]])
output, weights = scaled_dot_product_attention(Q, K, V)
print("Attention weights:\n", weights.round(3))
print("Output:\n", output.round(3))
# Each row shows how much attention to each token
7. Genetic Algorithm
import random
import numpy as np
class GeneticAlgorithm:
"""Genetic algorithm for function optimization."""
def __init__(self, population_size=50, mutation_rate=0.1,
crossover_rate=0.8):
self.pop_size = population_size
self.mutation_rate = mutation_rate
self.crossover_rate = crossover_rate
def initialize_population(self, chromosome_length):
return [np.random.randint(0, 2, chromosome_length).tolist()
for _ in range(self.pop_size)]
def fitness(self, chromosome):
"""Maximize: sum of bits (example: maximize number of 1s)"""
return sum(chromosome)
def selection(self, population, fitnesses):
"""Tournament selection"""
tournament = random.sample(range(self.pop_size), 3)
best = max(tournament, key=lambda i: fitnesses[i])
return population[best]
def crossover(self, parent1, parent2):
"""Single-point crossover"""
if random.random() < self.crossover_rate:
point = random.randint(1, len(parent1) - 1)
child = parent1[:point] + parent2[point:]
return child
return parent1[:]
def mutate(self, chromosome):
"""Bit-flip mutation"""
for i in range(len(chromosome)):
if random.random() < self.mutation_rate:
chromosome[i] = 1 - chromosome[i]
return chromosome
def evolve(self, chromosome_length=20, generations=100):
population = self.initialize_population(chromosome_length)
best_fitness_history = []
for gen in range(generations):
fitnesses = [self.fitness(c) for c in population]
best = max(fitnesses)
best_fitness_history.append(best)
# Create next generation
new_population = []
while len(new_population) < self.pop_size:
p1 = self.selection(population, fitnesses)
p2 = self.selection(population, fitnesses)
child = self.crossover(p1, p2)
child = self.mutate(child)
new_population.append(child)
population = new_population
final_fitnesses = [self.fitness(c) for c in population]
best_idx = np.argmax(final_fitnesses)
return population[best_idx], best_fitness_history
# Run
ga = GeneticAlgorithm(population_size=100, mutation_rate=0.01)
best, history = ga.evolve(chromosome_length=30, generations=200)
print(f"Best solution: {best}")
print(f"Best fitness: {sum(best)}/30")
8. Sentiment Analysis with TF-IDF + Naive Bayes
import numpy as np
from collections import defaultdict
class NaiveBayesClassifier:
"""Multinomial Naive Bayes for text classification."""
def __init__(self, alpha=1.0):
self.alpha = alpha # Laplace smoothing
def fit(self, X, y):
"""X: list of token lists, y: list of labels"""
self.classes = list(set(y))
self.class_prior = {}
self.word_prob = {c: defaultdict(lambda: self.alpha)
for c in self.classes}
self.vocab = set()
self.class_word_count = {c: 0 for c in self.classes}
# Count occurrences
for tokens, label in zip(X, y):
self.class_prior[label] = self.class_prior.get(label, 0) + 1
for word in tokens:
self.vocab.add(word)
self.word_prob[label][word] += 1
self.class_word_count[label] += 1
# Calculate priors
total = sum(self.class_prior.values())
for c in self.classes:
self.class_prior[c] = self.class_prior[c] / total
# Normalize word probabilities (log space)
V = len(self.vocab)
for c in self.classes:
total_words = self.class_word_count[c] + self.alpha * V
for word in self.vocab:
self.word_prob[c][word] = (
self.word_prob[c][word] / total_words
)
def predict(self, tokens):
scores = {}
for c in self.classes:
score = np.log(self.class_prior[c])
for word in tokens:
if word in self.vocab:
score += np.log(self.word_prob[c][word])
scores[c] = score
return max(scores, key=scores.get)
# Example
X_train = [["good", "great", "excellent"],
["bad", "terrible", "awful"],
["great", "amazing", "good"],
["poor", "bad", "horrible"]]
y_train = ["positive", "negative", "positive", "negative"]
nb = NaiveBayesClassifier()
nb.fit(X_train, y_train)
print(nb.predict(["good", "excellent"])) # positive
print(nb.predict(["bad", "horrible"])) # negative
9. Minimax with Alpha-Beta Pruning (Game AI)
def minimax(board, depth, alpha, beta, maximizing):
"""Minimax with alpha-beta pruning for Tic-Tac-Toe."""
winner = check_winner(board)
if winner == 'X':
return -10 + depth # Prefer faster wins
elif winner == 'O':
return 10 - depth
elif is_full(board):
return 0
if maximizing:
max_eval = -float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = 'O'
eval = minimax(board, depth+1, alpha, beta, False)
board[i][j] = ''
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Prune
return max_eval
else:
min_eval = float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = 'X'
eval = minimax(board, depth+1, alpha, beta, True)
board[i][j] = ''
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Prune
return min_eval
def best_move(board):
"""Find best move for 'O' using minimax."""
best_score = -float('inf')
move = (-1, -1)
for i in range(3):
for j in range(3):
if board[i][j] == '':
board[i][j] = 'O'
score = minimax(board, 0, -float('inf'),
float('inf'), False)
board[i][j] = ''
if score > best_score:
best_score = score
move = (i, j)
return move
10. GPT-style Tokenization & Embedding
from collections import Counter
import re
class SimpleTokenizer:
"""Byte-Pair Encoding (BPE) style tokenizer."""
def __init__(self, vocab_size=100):
self.vocab_size = vocab_size
self.vocab = {}
self.merges = []
def train(self, texts):
"""Train BPE tokenizer on corpus."""
# Start with individual characters
words = [' '.join(list(text)) for text in texts]
word_freqs = Counter(words)
while len(self.vocab) < self.vocab_size:
# Count pairs
pair_counts = Counter()
for word in word_freqs:
tokens = word.split()
for i in range(len(tokens) - 1):
pair = (tokens[i], tokens[i+1])
pair_counts[pair] += word_freqs[word]
if not pair_counts:
break
# Merge most frequent pair
best_pair = pair_counts.most_common(1)[0][0]
self.merges.append(best_pair)
# Replace in all words
new_word_freqs = Counter()
for word in word_freqs:
new_word = word.replace(
f"{best_pair[0]} {best_pair[1]}",
f"{best_pair[0]}{best_pair[1]}"
)
new_word_freqs[new_word] = word_freqs[word]
word_freqs = new_word_freqs
# Build vocabulary
self.vocab = {word: idx for idx, word in
enumerate(word_freqs.keys())}
def encode(self, text):
"""Encode text to token IDs."""
tokens = list(text)
for merge in self.merges:
new_tokens = []
i = 0
while i < len(tokens):
if i < len(tokens) - 1 and \
tokens[i] == merge[0] and tokens[i+1] == merge[1]:
new_tokens.append(merge[0] + merge[1])
i += 2
else:
new_tokens.append(tokens[i])
i += 1
tokens = new_tokens
return tokens
# Example
texts = ["low lower lowest", "new newer newest", "wide wider widest"]
tokenizer = SimpleTokenizer(vocab_size=20)
tokenizer.train(texts)
tokens = tokenizer.encode("lower")
print(f"Tokens: {tokens}")
Core Concepts
What is Artificial Intelligence?
Definition: AI is the simulation of human intelligence processes by machines, especially computer systems. These processes include learning, reasoning, self-correction, and perception.
Three Levels of AI:
- ANI (Narrow AI): Specialized in one task (chess engines, voice assistants, recommendation systems)
- AGI (General AI): Human-level intelligence across all domains (does not yet exist)
- ASI (Superintelligence): Surpasses human intelligence in all aspects (theoretical)
Machine Learning Fundamentals
Definition: A subset of AI where systems learn patterns from data without being explicitly programmed.
- Training: Model learns from labeled/unlabeled data by adjusting internal parameters
- Inference: Model makes predictions on new, unseen data
- Key Challenge: Generalizing from training data to unseen data
- Data Requirements: Quality and quantity of data often matter more than algorithm choice
Neural Networks & Deep Learning
Definition: Computational models inspired by biological neural networks, consisting of interconnected layers of nodes (neurons).
- Input Layer: Receives raw data features
- Hidden Layers: Learn hierarchical representations (edges → shapes → objects)
- Output Layer: Produces final prediction
- Backpropagation: Algorithm to compute gradients and update weights
- Activation Functions: ReLU, Sigmoid, Softmax — introduce non-linearity
Natural Language Processing (NLP)
Definition: AI field focused on enabling computers to understand, generate, and interact with human language.
- Tokenization: Breaking text into words/subwords/tokens
- Embeddings: Dense vector representations of words (Word2Vec, GloVe, BERT)
- Attention Mechanism: Model learns which words to focus on when processing text
- Transformers: Architecture using self-attention (GPT, BERT, T5)
- Large Language Models (LLMs): Trained on massive text corpora; can generate, summarize, translate
Reinforcement Learning
Definition: An agent learns to make decisions by interacting with an environment, receiving rewards/penalties.
- Agent: The learner/decision maker
- Environment: The world the agent interacts with
- State (s): Current situation of the agent
- Action (a): What the agent can do
- Reward (r): Feedback from the environment
- Policy π(a|s): Strategy the agent follows
- Q-Learning: Model-free RL using Q-values Q(s,a)
- Exploration vs Exploitation: Balance trying new actions vs. using known best actions
Computer Vision
Definition: AI field focused on enabling machines to interpret and understand visual information.
- Convolutional Neural Networks (CNNs): Specialized for image processing using convolutional filters
- Object Detection: Locate and classify objects (YOLO, Faster R-CNN)
- Image Segmentation: Classify each pixel (U-Net, Mask R-CNN)
- Image Classification: Assign label to entire image (ResNet, EfficientNet)
- Transfer Learning: Use pre-trained models on new tasks with less data
Search & Optimization
Definition: Finding the best solution from a set of possible solutions.
- Uninformed Search: BFS, DFS, Uniform Cost Search — no problem-specific knowledge
- Informed Search: A* with heuristic function h(n) to guide search
- Admissible Heuristic: Never overestimates true cost (guarantees A* optimality)
- Local Search: Hill climbing, simulated annealing, genetic algorithms
- Constraint Satisfaction: Find assignment satisfying constraints (CSP)
Ethics in AI
Key Concerns:
- Bias: Models can learn and amplify societal biases in training data
- Transparency: "Black box" models are hard to explain (Explainable AI / XAI)
- Privacy: Models may memorize and leak training data
- Fairness: Equal treatment across demographic groups
- Accountability: Who is responsible when AI causes harm?
- Job Displacement: Automation of tasks previously done by humans
Worked Examples
Example 1: Forward Propagation Calculation
Problem: Compute output of a 2-2-1 neural network for input [1, 0].
Given: W1=[[0.5, -0.6], [0.3, 0.8]], b1=[0.1, -0.2], W2=[[0.7, -0.4]], b2=[0.2]
Solution:
- Hidden layer pre-activation:
- z1₁ = 1×0.5 + 0×0.3 + 0.1 = 0.6
- z1₂ = 1×(-0.6) + 0×0.8 + (-0.2) = -0.8
- Hidden layer activation (sigmoid):
- a1₁ = σ(0.6) = 1/(1+e⁻⁰·⁶) = 0.646
- a1₂ = σ(-0.8) = 1/(1+e⁰·⁸) = 0.310
- Output pre-activation:
- z2 = 0.646×0.7 + 0.310×(-0.4) + 0.2 = 0.328
- Final output (sigmoid):
- ŷ = σ(0.328) = 1/(1+e⁻⁰·³²⁸) = 0.581
Example 2: Q-Learning Update
Problem: Given Q(s₁,a₂)=5, take action a₂, get reward r=10, move to s₂ where max Q(s₂,a)=8. Update Q(s₁,a₂) with α=0.5, γ=0.9.
Solution:
Q(s,a) ← Q(s,a) + α[r + γ·max Q(s',a') - Q(s,a)]
Q(s₁,a₂) = 5 + 0.5 × [10 + 0.9 × 8 - 5]
= 5 + 0.5 × [10 + 7.2 - 5]
= 5 + 0.5 × 12.2
= 5 + 6.1
= 11.1
Final Answer: Q(s₁,a₂) = 11.1
Example 3: A* Search Execution
Problem: Find path from S to G in a grid with obstacles.
Grid: S . . # . | . # . . . | . . . # . | . # . . G
Solution:
- Start: f(S)=h(S)=6 (Manhattan distance to G), g=0
- Expand S: neighbors right(1,0) f=6+1=7, down(0,1) f=6+1=7
- Expand (1,0): neighbor (2,0) f=5+2=7, (1,1) f=5+2=7
- Expand (2,0): neighbor (3,0) f=4+3=7, (2,1) f=4+3=7
- Continue expanding lowest f-cost nodes until reaching G
- Optimal path length: 6 steps
Example 4: Backpropagation Gradient
Problem: For a single neuron with sigmoid activation, compute the weight gradient. Input x=2, weight w=0.5, target y=1, output ŷ=σ(2×0.5)=σ(1)=0.731.
Solution:
- Loss: L = -[y·ln(ŷ) + (1-y)·ln(1-ŷ)] = -ln(0.731) = 0.313
- dL/dŷ = -(y/ŷ) + (1-y)/(1-ŷ) = -1/0.731 + 0 = -1.368
- dŷ/dz = ŷ(1-ŷ) = 0.731 × 0.269 = 0.197
- dz/dw = x = 2
- dL/dw = dL/dŷ × dŷ/dz × dz/dw = -1.368 × 0.197 × 2 = -0.539
- Weight update: w_new = 0.5 - 0.1×(-0.539) = 0.554
Example 5: Softmax Calculation
Problem: Given logits [2.0, 1.0, 0.1], compute softmax probabilities.
Solution:
- Subtract max for stability: [0, -1, -1.9]
- Exp: [e⁰, e⁻¹, e⁻¹·⁹] = [1.0, 0.368, 0.150]
- Sum: 1.0 + 0.368 + 0.150 = 1.518
- Divide: [1.0/1.518, 0.368/1.518, 0.150/1.518]
- Softmax: [0.659, 0.242, 0.112]
- Interpretation: Class 1 has 65.9% probability
Practice Problems
Problem 1: Implement Gradient Descent
Write a neural network weight update using gradient descent for MSE loss.
import numpy as np
def gradient_descent_step(X, y, weights, lr=0.01):
"""One step of gradient descent for linear regression."""
n = len(y)
predictions = X @ weights
errors = predictions - y
gradient = (2/n) * X.T @ errors
weights -= lr * gradient
mse = np.mean(errors**2)
return weights, mse
# Example
X = np.array([[1, 2], [2, 3], [3, 4], [4, 5]])
y = np.array([3, 5, 7, 9])
w = np.array([0.0, 0.0])
for epoch in range(100):
w, loss = gradient_descent_step(X, y, w, lr=0.01)
if epoch % 25 == 0:
print(f"Epoch {epoch}: w={w.round(3)}, MSE={loss:.4f}")
Problem 2: Implement K-Nearest Neighbors
Write a KNN classifier from scratch.
import numpy as np
from collections import Counter
def euclidean_distance(a, b):
return np.sqrt(np.sum((a - b) ** 2))
def knn_classify(X_train, y_train, test_point, k=3):
"""K-Nearest Neighbors classification."""
distances = []
for i, train_point in enumerate(X_train):
dist = euclidean_distance(test_point, train_point)
distances.append((dist, y_train[i]))
distances.sort()
k_nearest = distances[:k]
k_labels = [label for _, label in k_nearest]
return Counter(k_labels).most_common(1)[0][0]
# Example: Classify fruits (apple=0, banana=1)
X_train = np.array([[130, 0], [140, 0], [150, 1], [170, 1]])
# Features: [weight, elongated]
y_train = np.array([0, 0, 1, 1])
test = np.array([160, 1])
prediction = knn_classify(X_train, y_train, test, k=3)
print(f"Prediction: {'banana' if prediction == 1 else 'apple'}") # banana
Problem 3: Beam Search Decoding
Implement beam search for sequence generation with beam width 2.
import heapq
def beam_search(initial_token, get_next_probs, beam_width=2, max_length=5):
"""Beam search for sequence generation."""
beams = [(0.0, [initial_token])] # (log_prob, sequence)
for _ in range(max_length):
candidates = []
for log_prob, sequence in beams:
probs = get_next_probs(sequence)
for token, prob in probs:
new_prob = log_prob + np.log(prob + 1e-10)
candidates.append((new_prob, sequence + [token]))
# Keep top-k beams
candidates.sort(reverse=True)
beams = candidates[:beam_width]
return beams
# Example: At each step, choose from 3 possible next tokens
# with different probabilities
Problem 4: Implement Word2Vec Skip-gram
Write the forward pass and loss function for a skip-gram model.
import numpy as np
class SkipGram:
"""Simplified Skip-gram Word2Vec model."""
def __init__(self, vocab_size, embedding_dim):
self.W_in = np.random.randn(vocab_size, embedding_dim) * 0.01
self.W_out = np.random.randn(embedding_dim, vocab_size) * 0.01
def forward(self, target_idx, context_indices):
"""Forward pass for one target-context pair."""
# Get embedding for target word
h = self.W_in[target_idx] # (embedding_dim,)
# Compute scores for all words in vocab
scores = self.W_out.T @ h # (vocab_size,)
# Softmax
scores = scores - np.max(scores)
exp_scores = np.exp(scores)
probs = exp_scores / exp_scores.sum()
# Negative log-likelihood loss
loss = -sum(np.log(probs[ctx] + 1e-10) for ctx in context_indices)
return loss, probs
def get_embedding(self, word_idx):
return self.W_in[word_idx]
Problem 5: Monte Carlo Tree Search (MCTS)
Implement the UCB1 formula for node selection in MCTS.
import math
import numpy as np
class MCTSNode:
def __init__(self, state, parent=None):
self.state = state
self.parent = parent
self.children = []
self.visits = 0
self.wins = 0
def ucb1(self, exploration_const=1.414):
"""UCB1 formula for balancing exploration/exploitation."""
if self.visits == 0:
return float('inf')
exploitation = self.wins / self.visits
exploration = exploration_const * math.sqrt(
math.log(self.parent.visits) / self.visits
)
return exploitation + exploration
def select_child(self):
"""Select child with highest UCB1 score."""
return max(self.children, key=lambda c: c.ucb1())
def expand(self, action, state):
"""Add a new child node."""
child = MCTSNode(state, parent=self)
self.children.append(child)
return child
def update(self, result):
"""Backpropagate result up the tree."""
self.visits += 1
self.wins += result
Problem 6: LSTM Cell Implementation
Implement the forward pass of an LSTM cell.
import numpy as np
def sigmoid(x):
return 1 / (1 + np.exp(-np.clip(x, -500, 500)))
def lstm_cell(x_t, h_prev, c_prev, W_f, W_i, W_c, W_o, b_f, b_i, b_c, b_o):
"""Single LSTM cell forward pass."""
# Forget gate
f_t = sigmoid(W_f @ np.concatenate([h_prev, x_t]) + b_f)
# Input gate
i_t = sigmoid(W_i @ np.concatenate([h_prev, x_t]) + b_i)
# Candidate cell state
c_tilde = np.tanh(W_c @ np.concatenate([h_prev, x_t]) + b_c)
# Update cell state
c_t = f_t * c_prev + i_t * c_tilde
# Output gate
o_t = sigmoid(W_o @ np.concatenate([h_prev, x_t]) + b_o)
# Hidden state
h_t = o_t * np.tanh(c_t)
cache = (f_t, i_t, c_tilde, c_prev, o_t, h_prev, x_t)
return h_t, c_t, cache
Problem 7: TF-IDF Vectorization
Implement TF-IDF from scratch for a corpus of documents.
import numpy as np
import math
def compute_tf_idf(documents):
"""Compute TF-IDF vectors for a list of documents."""
# Tokenize
tokenized = [doc.lower().split() for doc in documents]
# Vocabulary
vocab = sorted(set(word for doc in tokenized for word in doc))
word_to_idx = {w: i for i, w in enumerate(vocab)}
n_docs = len(documents)
n_words = len(vocab)
# Term Frequency
tf = np.zeros((n_docs, n_words))
for i, doc in enumerate(tokenized):
for word in doc:
tf[i, word_to_idx[word]] += 1
tf[i] /= len(doc) if doc else 1 # Normalize
# Inverse Document Frequency
df = np.array([sum(1 for doc in tokenized if word in doc)
for word in vocab])
idf = np.log((1 + n_docs) / (1 + df)) + 1
# TF-IDF
tf_idf = tf * idf
# L2 normalize
norms = np.linalg.norm(tf_idf, axis=1, keepdims=True)
norms[norms == 0] = 1
tf_idf = tf_idf / norms
return tf_idf, vocab
# Example
docs = ["cat sat on mat", "dog sat on log", "cat chased dog"]
vectors, vocab = compute_tf_idf(docs)
print("Vocabulary:", vocab)
print("TF-IDF shape:", vectors.shape)
Problem 8: Multi-Armed Bandit (Epsilon-Greedy)
Implement epsilon-greedy strategy for the multi-armed bandit problem.
import numpy as np
class EpsilonGreedyBandit:
"""Epsilon-greedy multi-armed bandit agent."""
def __init__(self, n_arms, epsilon=0.1):
self.n_arms = n_arms
self.epsilon = epsilon
self.counts = np.zeros(n_arms)
self.values = np.zeros(n_arms)
def select_arm(self):
if np.random.random() < self.epsilon:
return np.random.randint(self.n_arms) # Explore
return np.argmax(self.values) # Exploit
def update(self, arm, reward):
self.counts[arm] += 1
n = self.counts[arm]
# Incremental mean update
self.values[arm] = ((n-1)/n) * self.values[arm] + (1/n) * reward
# Simulate
np.random.seed(42)
true_means = [0.2, 0.5, 0.75]
bandit = EpsilonGreedyBandit(n_arms=3, epsilon=0.1)
for t in range(1000):
arm = bandit.select_arm()
reward = 1 if np.random.random() < true_means[arm] else 0
bandit.update(arm, reward)
print(f"Estimated values: {bandit.values.round(3)}")
print(f"Pulls per arm: {bandit.counts}") # Best arm (2) gets most pulls
Problem 9: Knowledge Graph Embedding (TransE)
Implement the TransE scoring function and loss.
import numpy as np
def transE_score(head, relation, tail):
"""TransE scoring: -||h + r - t||₁ (lower is better)."""
return -np.linalg.norm(head + relation - tail, ord=1)
def transE_loss(pos_triples, neg_triples, margin=1.0):
"""Margin-based ranking loss for TransE."""
loss = 0
for (h, r, t) in pos_triples:
pos_score = transE_score(h, r, t)
for (h_neg, r_neg, t_neg) in neg_triples:
neg_score = transE_score(h_neg, r_neg, t_neg)
loss += max(0, margin + pos_score - neg_score)
return loss
# Example: (Paris, capital_of, France)
h = np.array([0.5, 0.3]) # Paris embedding
r = np.array([0.1, 0.1]) # capital_of relation
t = np.array([0.6, 0.4]) # France embedding
score = transE_score(h, r, t)
print(f"TransE score: {score:.3f}") # Close to 0 if correct
Problem 10: Model Calibration
Implement Platt scaling for calibrating classifier outputs.
import numpy as np
class PlattScaling:
"""Platt scaling: fit sigmoid to classifier scores."""
def __init__(self):
self.A = 0
self.B = 0
def _sigmoid(self, x):
return 1 / (1 + np.exp(-np.clip(x, -500, 500)))
def fit(self, scores, labels):
"""Fit sigmoid parameters A, B such that P(y=1|x) = 1/(1+exp(A*x+B))"""
# Simplified: use gradient descent
self.A, self.B = 0.0, 0.0
lr = 0.01
for _ in range(1000):
probs = self._sigmoid(self.A * scores + self.B)
error = probs - labels
dA = np.mean(error * scores)
dB = np.mean(error)
self.A -= lr * dA
self.B -= lr * dB
def predict_proba(self, scores):
return self._sigmoid(self.A * scores + self.B)
# Example
scores = np.array([0.1, 0.4, 0.35, 0.8, 0.9, 0.7, 0.2, 0.6])
labels = np.array([0, 0, 0, 1, 1, 1, 0, 1])
calibrator = PlattScaling()
calibrator.fit(scores, labels)
probs = calibrator.predict_proba(scores)
print(f"Calibrated probabilities: {probs.round(3)}")