Linear regression is a method that uses a linear funcsion to fit data points by minimizing the squared error between predicted and actual values. This approach can be viewed as a convex quadratic optimization problem, where the optimal solution occurs when the derivative of the objective function is zero. When the number of samples exceeds the number of features, the matrix is invertible, allowing for a closed-form solution. However, when the number of features exceeds the number of samples, the matrix may not be invertible, leading to multiple solutions. In such cases, regularization techniques like ridge and lasso regression are used to prevent overfitting and simplify the model.

Ridge regression adds a penalty term based on the L2 norm of the coefficients, which helps in making the model more robust and ensures the matrix is invertible. Lasso regression, on the other hand, uses the L1 norm to encourage sparsity in the coefficients, resulting in fewer non-zero parameters.

From a probabilistic perspective, the least squares loss function assumes that errors follow a Gaussian distribution. Maximum likelihood estimation leads to minimizing the sum of squared residuals, which aligns with the linear rgeression framework.

To handle non-linear relationships, linear models can be extended using transformations or weighted approaches. Local weighted linear regression assigns weights to data points based on their proximity to the prediction point, allowing for localized fitting and improved performance on non-linear data.

The following code examples demonstrate the implementation of these regression methods:

/**
This function implements linear regression by solving the normal equation.
It computes the optimal weights by inverting the matrix xT * x and multiplying it with xT * y.
**/
int regression(Matrix x, Matrix y) {
    Matrix xT = x.transposeMatrix();
    Matrix xTx = xTx.multsMatrix(xT, x);
    Matrix xTx_1 = xTx.niMatrix();
    Matrix xTx_1xT = xTx_1xT.multsMatrix(xTx_1, xT);
    Matrix ws = ws.multsMatrix(xTx_1xT, y);
    cout << "ws" << endl;
    ws.print();
    return 0;
}

/**
This function extends linear regression by adding a ridge penalty to the diagonal of the matrix xT * x.
The penalty term helps in ensuring matrix invertibility and prevents overfitting.
**/
int ridgeRegres(Matrix x, Matrix y, double lam) {
    Matrix xT = x.transposeMatrix();
    Matrix xTx = xTx.multsMatrix(xT, x);
    Matrix denom(xTx.row, xTx.col, lam, "diag");
    xTx = xTx.addMatrix(xTx, denom);
    Matrix xTx_1 = xTx.niMatrix();
    Matrix xTx_1xT = xTx_1xT.multsMatrix(xTx_1, xT);
    Matrix ws = ws.multsMatrix(xTx_1xT, y);
    cout << "ws" << endl;
    ws.print();
    return 0;
}

/**
This function performs local weighted linear regression, assigning different weights to data points based on their distance from the test point.
A Gaussian kernel is used to calculate the weights, which allows for localized fitting and better performance on non-linear data.
**/
Matrix locWeightLineReg(Matrix test, Matrix x, Matrix y, const double &k) {
    Matrix w(x.row, x.row, 0, "T");
    double temp = 0;
    int i, j;

    for (i = 0; i < x.row; i++) {
        temp = 0;
        for (j = 0; j < x.col; j++) {
            temp += (test.data[0][j] - x.data[i][j]) * (test.data[0][j] - x.data[i][j]);
        }
        w.data[i][i] = exp(temp / (-2.0 * k * k));
    }

    Matrix xT = x.transposeMatrix();
    Matrix wx = wx.multsMatrix(w, x);
    Matrix xTwx = xTwx.multsMatrix(xT, wx);
    Matrix xTwx_1 = xTwx.niMatrix();
    Matrix xTwx_1xT = xTwx_1xT.multsMatrix(xTwx_1, xT);
    Matrix xTwx_1xTw = xTwx_1xTw.multsMatrix(xTwx_1xT, w);
    Matrix ws = xTwx_1xTw * y;
    return ws;
}

For more details, refer to the full implementation: https://link.zhihu.com/?target=https%3A//github.com/myazi/myLearn/blob/master/LineReg.cpp