Simple Linear Regression

easyFREELinear RegressionMachine 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

Inputs: X holds the $n = 5$ positions $x_i = 1,\dots,5$ and y the observed values $2, 4, 5, 4, 5$ at those positions. We want the line $y = mx + b$ minimising squared vertical error.
The four sums: $\sum x_i = 15$ , $\sum y_i = 20$ , $\sum x_i y_i = 2 + 8 + 15 + 16 + 25 = 66$ and $\sum x_i^2 = 1 + 4 + 9 + 16 + 25 = 55$ .
Slope: $m = \frac{5 \cdot 66 - 15 \cdot 20}{5 \cdot 55 - 15^2} = \frac{330 - 300}{275 - 225} = \frac{30}{50} = 0.6$ . Each unit of $x$ adds $0.6$ to the fitted $y$ .
Intercept: the means are $\bar{x} = 3$ and $\bar{y} = 4$ , so $b = 4 - 0.6 \times 3 = 2.2$ .
Output: the pair (0.6, 2.2), slope first, each rounded to 4 decimal places.
Notice that the line passes through the mean point $(3, 4)$ . Its predictions $2.8, 3.4, 4.0, 4.6, 5.2$ leave residuals $-0.8, 0.6, 1.0, -0.6, -0.2$ , which sum to zero.

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)

Learn this in

Linear AlgebraFoundations Linear RegressionML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

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