Problem: Linear Regression from Scratch

Difficulty: medium
Points: 150
Time Limit: 60 seconds
Memory Limit: 512 MB

---

Problem Description

Implement linear regression from scratch using gradient descent.

Part 1: Cost Function

Implement the mean squared error cost function.

Question Type: code
Requirements:

• Function should take X, y, theta as parameters
• Return scalar cost value

Starter Code:

```python
def mean_squared_error(X, y, theta):
    """
    Calculate mean squared error cost function.
    
    Parameters:
    X: feature matrix (m, n)
    y: target vector (m,)
    theta: parameter vector (n,)
    
    Returns:
    cost: scalar cost value
    """
    # Your code here
    pass
```

Test Code:

```python
def test():
    # Method 1: Compare with reference implementation
    def mean_squared_error_real(X, y, theta):
        m = len(y)
        predictions = X @ theta
        return (1 / (2 * m)) * np.sum((predictions - y) ** 2)
    
    # Test with sample data
    X = np.array([[1, 2], [3, 4], [5, 6]])
    y = np.array([3, 7, 11])
    theta = np.array([1.0, 1.0])
    
    # Test the implementation
    result = mean_squared_error(X, y, theta)
    expected = mean_squared_error_real(X, y, theta)
    
    return abs(result - expected) < 1e-10
```

Part 2: Mathematical Formula

Write the gradient formula.

Question Type: math
Expected: $\frac{\partial J}{\partial \theta} = \frac{1}{m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}$

Part 3: Multiple Choice

What is the main advantage of stochastic gradient descent?

Question Type: multiple_choice
Options:

• A) More accurate results
• B) Faster convergence for large datasets
• C) Less memory usage
• D) Better for non-convex functions

Correct Answer: B

Part 4: Gradient Descent Implementation

Implement the gradient descent algorithm for linear regression.

Question Type: code
Requirements:

• Function should take X, y, learning_rate, num_iterations as parameters
• Return weights, bias, and cost history

Starter Code:

```python
def gradient_descent(X, y, learning_rate=0.01, num_iterations=1000):
    """
    Implement gradient descent for linear regression.
    
    Parameters:
    X: feature matrix (m, n)
    y: target vector (m,)
    learning_rate: step size
    num_iterations: number of iterations
    
    Returns:
    weights: learned weights (n,)
    bias: learned bias term
    costs: list of cost values
    """
    # Your code here
    pass
```

Test Code:

```python
def test():
    # Method 1: Compare with reference implementation
    def gradient_descent_real(X, y, learning_rate=0.01, num_iterations=1000):
        m, n = X.shape
        weights = np.zeros(n)
        bias = 0
        costs = []
        
        for i in range(num_iterations):
            predictions = X @ weights + bias
            error = predictions - y
            dw = (1 / m) * X.T @ error
            db = (1 / m) * np.sum(error)
            weights -= learning_rate * dw
            bias -= learning_rate * db
            cost = (1 / (2 * m)) * np.sum(error ** 2)
            costs.append(cost)
        
        return weights, bias, costs
    
    # Test with sample data
    X = np.array([[1, 2], [3, 4], [5, 6]])
    y = np.array([3, 7, 11])
    
    # Test the implementation
    weights, bias, costs = gradient_descent(X, y, 0.01, 100)
    weights_real, bias_real, costs_real = gradient_descent_real(X, y, 0.01, 100)
    
    return (np.allclose(weights, weights_real, atol=1e-6) and 
            abs(bias - bias_real) < 1e-6 and
            len(costs) == len(costs_real))
```