📘

Simple Linear Regression

EasyLinear Regression 📚 Machine Learning 1

Implement simple linear regression using the closed-form (least squares) solution.

Given a list of $x$ values and a list of $y$ values, compute the slope $m$ and intercept $b$ of the best-fit line $y = mx + b$ .

The formulas are: $m = \frac{n\sum x_i y_i - \sum x_i \sum y_i}{n\sum x_i^2 - (\sum x_i)^2}$ $b = \bar{y} - m\bar{x}$

where $n$ is the number of data points and $\bar{x}$ , $\bar{y}$ are the means.

Return a tuple (slope, intercept), both rounded to 4 decimal places.

Example:

Input:

X = [1, 2, 3, 4, 5]
y = [2, 4, 5, 4, 5]

Output:

(0.6, 2.2)

Reasoning:

First, we calculate the necessary sums: $\sum x_i = 1 + 2 + 3 + 4 + 5 = 15$ , $\sum y_i = 2 + 4 + 5 + 4 + 5 = 20$ , $\sum x_i y_i = 1*2 + 2*4 + 3*5 + 4*4 + 5*5 = 2 + 8 + 15 + 16 + 25 = 66$ , and $\sum x_i^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 1 + 4 + 9 + 16 + 25 = 55$ .
Then, we calculate the slope $m$ using the formula: $m = \frac{5*66 - 15*20}{5*55 - 15^2} = \frac{330 - 300}{275 - 225} = \frac{30}{50} = 0.6$ .
Next, we calculate the means: $\bar{x} = \frac{15}{5} = 3$ and $\bar{y} = \frac{20}{5} = 4$ , and then the intercept $b = \bar{y} - m\bar{x} = 4 - 0.6*3 = 4 - 1.8 = 2.2$ .
The final output is a tuple of the slope and intercept, both rounded to 4 decimal places: $(0.6, 2.2)$ .

Constraints:

Input: two lists of equal length (at least 2 elements)
Return a tuple (slope, intercept) rounded to 4 decimal places
Use only basic Python (no numpy)

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

Background Knowledge

Linear Regression is a fundamental concept in Machine Learning that involves modeling the relationship between a dependent variable (target) and one or more independent variables (features) using a linear equation. In Simple Linear Regression, we have only one independent variable, and the goal is to find the best-fit line that minimizes the difference between the observed data points and the predicted values. The equation of the best-fit line is given by $y = mx + b$ , where $m$ is the slope and $b$ is the intercept.

The closed-form (least squares) solution is a method for finding the optimal values of $m$ and $b$ by minimizing the sum of the squared errors between the observed and predicted values. This approach is based on the principle of ordinary least squares (OLS), which aims to find the parameters that result in the smallest possible sum of squared residuals. The formulas provided in the problem description are derived from this principle and are used to compute the slope and intercept of the best-fit line.

In order to apply these formulas, we need to calculate various quantities such as the mean of the $x$ and $y$ values, the sum of the products of $x$ and $y$ , and the sum of the squares of the $x$ values. These calculations are essential for finding the optimal values of $m$ and $b$ that result in the best-fit line.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Calculate the necessary quantities such as the mean of the $x$ and $y$ values, the sum of the products of $x$ and $y$ , and the sum of the squares of the $x$ values.
Use these quantities to compute the slope and intercept of the best-fit line using the provided formulas.
Return the computed slope and intercept as a tuple, rounded to the specified number of decimal places.

Step-by-Step Strategy

To implement the solution, follow these steps:

Calculate the mean of the $x$ values ( $\bar{x}$ ) and the mean of the $y$ values ( $\bar{y}$ ).
Compute the sum of the products of $x$ and $y$ ( $\sum x_i y_i$ ) and the sum of the squares of the $x$ values ( $\sum x_i^2$ ).
Use the calculated quantities to compute the slope ( $m$ ) using the formula: $m = \frac{n\sum x_i y_i - \sum x_i \sum y_i}{n\sum x_i^2 - (\sum x_i)^2}$ .
Compute the intercept ( $b$ ) using the formula: $b = \bar{y} - m\bar{x}$ .
Return the computed slope and intercept as a tuple, rounded to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the calculations are performed correctly, and the formulas are applied as given.
Be mindful of the order of operations and the use of parentheses to avoid errors.
Make sure to round the computed slope and intercept to the specified number of decimal places.

Time & Space Complexity

The expected time complexity of the solution is O(n), where n is the number of data points, since we need to iterate over the data points to calculate the necessary quantities. The space complexity is O(1), since we only need to store a constant amount of space to store the calculated quantities and the computed slope and intercept.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.