📘

Weighted Least Squares

Implement a weighted least squares method to fit a line to a set of points, where each point has a weight indicating its importance. This technique is crucial in model fitting and optimization as it allows for more accurate predictions by giving more influence to certain points.

The concept of weighted least squares is an extension of the ordinary least squares method, which minimizes the sum of the squared errors between observed responses and predicted responses. In weighted least squares, each point is assigned a weight $w_i$ , and the goal is to minimize the weighted sum of the squared errors $E = \sum_i w_i(y_i - (mx_i + b))^2$ .

Here are the steps to achieve this:

Calculate the weighted sum of $x$ values, $y$ values, $x^2$ values, and $xy$ values.
Use these weighted sums to calculate the slope $m$ and intercept $b$ of the line.

E = \sum_i w_i(y_i - (mx_i + b))^2

This technique is widely used in computer vision applications.

Example:

Input:

weighted_fit_line([(0,0,1), (1,2,1), (2,2,2)])

Output:

[1.0, 0.25]

Reasoning:

First, list the data with weights: $(x_i, y_i, w_i) = (0,0,1), (1,2,1), (2,2,2)$ , and compute weighted sums: $\sum w_i = 4$ , $\sum w_ix_i = 0\cdot1 + 1\cdot1 + 2\cdot2 = 5$ , $\sum w_iy_i = 0\cdot1 + 2\cdot1 + 2\cdot2 = 6$ , $\sum w_ix_i^2 = 0^2\cdot1 + 1^2\cdot1 + 2^2\cdot2 = 9$ , $\sum w_ix_iy_i = 0\cdot0\cdot1 + 1\cdot2\cdot1 + 2\cdot2\cdot2 = 12$ .
Then, use the weighted least squares formulas for slope $m$ and intercept $b$ :
- $m = \dfrac{\sum w_i x_i y_i - \frac{1}{\sum w_i}(\sum w_i x_i)(\sum w_i y_i)}{\sum w_i x_i^2 - \frac{1}{\sum w_i}(\sum w_i x_i)^2} = \dfrac{12 - \frac{5\cdot6}{4}}{9 - \frac{5^2}{4}} = \dfrac{4.5}{4.5} = 1.0$
- $b = \dfrac{\sum w_i y_i - m \sum w_i x_i}{\sum w_i} = \dfrac{6 - 1\cdot5}{4} = 0.25$
The final output is the fitted line parameters $[m, b] = [1.0, 0.25]`.

Constraints:

points is a list of (x, y, weight) tuples
Return [m, b] rounded to 4 decimal places

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘