01.1c_Linear Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c97b1183-e543-4c6e-bd3c-2b02b95b8bbc",
   "metadata": {},
   "source": [
    "## 1.1. Linear Models"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c67f5873-efff-4fbe-84b9-d2c4e7a9009b",
   "metadata": {},
   "source": [
    "### 1.1.5. Elastic-Net"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e469bc9f-de5c-4512-ad7e-2a1ff0168730",
   "metadata": {},
   "source": [
    "[ElasticNet](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.ElasticNet.html#sklearn.linear_model.ElasticNet) is a linear regression model trained with both $\\ell_1$ and $\\ell_2$-norm regularization of the coefficients. This combination allows for learning a sparse model where few of the weights are non-zero like [Lasso](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Lasso.html#sklearn.linear_model.Lasso), while still maintaining the regularization properties of [Ridge](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Ridge.html#sklearn.linear_model.Ridge). We control the convex combination of $\\ell_1$ and $\\ell_2$ using the `l1_ratio` parameter.\n",
    "\n",
    "Elastic-net is useful when there are multiple features that are correlated with one another. Lasso is likely to pick one of these at random, while elastic-net is likely to pick both.\n",
    "\n",
    "A practical advantage of trading-off between Lasso and Ridge is that it allows Elastic-Net to inherit some of Ridge’s stability under rotation.\n",
    "\n",
    "The objective function to minimize is in this case\n",
    "\n",
    "$$\\min_w \\frac{1}{2n_{samples}} \\lVert Xw - y \\rVert_2^2 + \\alpha \\rho \\lVert w \\rVert_1 + \\frac{\\alpha(1 - \\rho)}{2} \\lVert w \\rVert_2^2$$\n",
    "\n",
    "<center><img src=\"https://scikit-learn.org/stable/_images/sphx_glr_plot_lasso_lasso_lars_elasticnet_path_002.png\" /></center>\n",
    "\n",
    "The class [ElasticNetCV](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.ElasticNetCV.html#sklearn.linear_model.ElasticNetCV) can be used to set the parameters `alpha` $(\\alpha)$ and `l1_ratio` $(\\rho)$ by cross-validation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c49db75e-e003-4847-a854-59855c3c4d96",
   "metadata": {},
   "source": [
    "$\\textbf{Examples}$\n",
    "- L1-based models for Sparse Signals - [Sci-kit Link](https://scikit-learn.org/stable/auto_examples/linear_model/plot_lasso_and_elasticnet.html#sphx-glr-auto-examples-linear-model-plot-lasso-and-elasticnet-py) | [Python code](https://github.com/baksho/ml-handson/blob/main/Examples/06_example_plot_lasso_and_elasticnet.py) | [Jupyter Notebook](https://github.com/baksho/ml-handson/blob/main/Examples/06_example_plot_lasso_and_elasticnet.ipynb)\n",
    "- Lasso and Elastic Net - [Sci-kit Link](https://scikit-learn.org/stable/auto_examples/linear_model/plot_lasso_coordinate_descent_path.html#sphx-glr-auto-examples-linear-model-plot-lasso-coordinate-descent-path-py) | [Python code](https://github.com/baksho/ml-handson/blob/main/Examples/11_example_plot_lasso_coordinate_descent_path.py) | [Jupyter Notebook](https://github.com/baksho/ml-handson/blob/main/Examples/11_example_plot_lasso_coordinate_descent_path.ipynb)\n",
    "- Fitting an Elastic Net with a precomputed Gram Matrix and Weighted Samples - [Sci-kit Link](https://scikit-learn.org/stable/auto_examples/linear_model/plot_elastic_net_precomputed_gram_matrix_with_weighted_samples.html#sphx-glr-auto-examples-linear-model-plot-elastic-net-precomputed-gram-matrix-with-weighted-samples-py) | [Python code](https://github.com/baksho/ml-handson/blob/main/Examples/12_example_plot_elastic_net_precomputed_gram_matrix_with_weighted_samples.py) | [Jupyter Notebook](https://github.com/baksho/ml-handson/blob/main/Examples/12_example_plot_elastic_net_precomputed_gram_matrix_with_weighted_samples.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78d25ea0-ce2d-46c0-afa3-f35ac316a74b",
   "metadata": {},
   "source": [
    "$\\textbf{References}$\n",
    "\n",
    "The following two references explain the iterations used in the coordinate descent solver of scikit-learn, as well as the duality gap computation used for convergence control.\n",
    "\n",
    "- *“Regularization Path For Generalized linear Models by Coordinate Descent”*, Friedman, Hastie & Tibshirani, J Stat Softw, 2010 ([Paper](https://www.jstatsoft.org/article/view/v033i01/v33i01.pdf)).\n",
    "- *“An Interior-Point Method for Large-Scale L1-Regularized Least Squares”*, S. J. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinevsky, in IEEE Journal of Selected Topics in Signal Processing, 2007 ([Paper](https://web.stanford.edu/~boyd/papers/pdf/l1_ls.pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f985eac1-275a-4f03-a7ea-b986b3e6724f",
   "metadata": {},
   "source": [
    "### 1.1.6. Multi-task Elastic-Net"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6878183-d391-4c6b-996e-62874998e950",
   "metadata": {},
   "source": [
    "The [MultiTaskElasticNet](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.MultiTaskElasticNet.html#sklearn.linear_model.MultiTaskElasticNet) is an elastic-net model that estimates sparse coefficients for multiple regression problems jointly: $Y$ is a 2D array of shape `(n_samples, n_tasks)`. The constraint is that the selected features are the same for all the regression problems, also called tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "264ce0d0-a233-4f80-801f-6c0d8967d4e0",
   "metadata": {},
   "source": [
    "Mathematically, it consists of a linear model trained with a mixed $\\ell_1 \\ell_2$-norm and $\\ell_2$-norm for regularization. The objective function to minimize is:\n",
    "\n",
    "$$\\min_W \\frac{1}{2n_{samples}} \\lVert XW - y \\rVert_{Fro}^2 + \\alpha \\rho \\lVert W \\rVert_{21} + \\frac{\\alpha(1 - \\rho)}{2} \\lVert W \\rVert_{Fro}^2$$\n",
    "\n",
    "The implementtion in the class :class:`~sklearn.linear_model.MultiTaskElasticNet` uses coordinate descent as the algorithm to fit the coefficints.\n",
    "\n",
    "The class [MultiTaskElasticNetCV](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.MultiTaskElasticNetCV.html#sklearn.linear_model.MultiTaskElasticNetCV) can be used to set the parameters `alpha` $(\\alpha)$ and `l1_ratio` $(\\rho)$ by cross-validation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5156027-db1e-4eb7-b6fa-04be5407acf9",
   "metadata": {},
   "source": [
    "### 1.1.7. Least Angle Regression"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd36e064-c4f1-4497-9fc1-02637824404f",
   "metadata": {},
   "source": [
    "Least-angle regression (LARS) is a regression algorithm for high-dimensional data, developed by Bradley Efron, Trevor Hastie, Iain Johnstone and Robert Tibshirani. LARS is similar to forward stepwise regression. At each step, it finds the feature most correlated with the target. When there are multiple features having equal correlation, instead of continuing along the same feature, it proceeds in a direction equiangular between the features.\n",
    "\n",
    "The advantages of LARS are:\n",
    "- It is numerically efficient in contexts where the number of features is significantly greater than the number of samples.\n",
    "- It is computationally just as fast as forward selection and has the same order of complexity as ordinary least squares.\n",
    "- It produces a full piecewise linear solution path, which is useful in cross-validation or similar attempts to tune the model.\n",
    "- If two features are almost equally correlated with the target, then their coefficients should increase at approximately the same rate. The algorithm thus behaves as intuition would expect, and also is more stable.\n",
    "- It is easily modified to produce solutions for other estimators, like the Lasso.\n",
    "\n",
    "This disadvantage of the LARS method include:\n",
    "- Because LARS is based upon an iterative refitting of the residuals, it would appear to be especially sensitive to the effects of noise. This problem is discussed in detail by Weisberg in the discussion section of the Efron et al. (2004) Annals of Statistics article.\n",
    "\n",
    "The LARS model can be used via the estimator [Lars](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Lars.html#sklearn.linear_model.Lars), or its low-level implementation [lars_path](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.lars_path.html#sklearn.linear_model.lars_path) or [lars_path_gram](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.lars_path_gram.html#sklearn.linear_model.lars_path_gram)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d777ab4c-2a03-42eb-8b95-33759c23a217",
   "metadata": {},
   "source": [
    "### 1.1.8. LARS Lasso"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f14a92ba-3cc9-4415-8d46-e230ba2276bd",
   "metadata": {},
   "source": [
    "[LassoLars](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LassoLars.html#sklearn.linear_model.LassoLars) is a lasso model implemented using the LARS algorithm, and unlike the implementation based on coordinate descent, this yields the exact solution, which is piecewise linear as a function of the norm of its coefficients.\n",
    "\n",
    "<center><img src=\"https://scikit-learn.org/stable/_images/sphx_glr_plot_lasso_lasso_lars_elasticnet_path_001.png\" /></center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "42402bad-a921-4d0e-a9bf-e57683d95199",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.6, 0. ])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn import linear_model\n",
    "reg = linear_model.LassoLars(alpha=.1)\n",
    "reg.fit([[0, 0], [1, 1]], [0, 1])\n",
    "reg.coef_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c99a149d-f8bc-413c-9a4f-040e52bc6c70",
   "metadata": {},
   "source": [
    "$\\textbf{Example}$\n",
    "- Lasso path using LARS - [Sci-kit Link](https://scikit-learn.org/stable/auto_examples/linear_model/plot_lasso_lars.html#sphx-glr-auto-examples-linear-model-plot-lasso-lars-py) | [Python code](https://github.com/baksho/ml-handson/blob/main/Examples/13_example_plot_lasso_lars.py) | [Jupyter Notebook](https://github.com/baksho/ml-handson/blob/main/Examples/13_example_plot_lasso_lars.ipynb)\n",
    "\n",
    "The Lars algorithm provides the full path of the coefficients along the regularization parameter almost for free, thus a common operation is to retrieve the path with one of the functions `~sklearn.linear_model.lars_path` or `~sklearn.linear_model.lars_path_gram`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d25af7ce-7165-4ad7-b4df-e8777269a47a",
   "metadata": {},
   "source": [
    "$\\textbf{Mathematical Formulation}$\n",
    "\n",
    "The algorithm is similar to forward stepwise regression, but instead of including features at each step, the estimated coefficients are increased in a direction equiangular to each one’s correlations with the residual.\n",
    "\n",
    "Instead of giving a vector result, the LARS solution consists of a curve denoting the solution for each value of the $\\ell_1$-norm of the parameter vector. The full coefficients path is stored in the array `coef_path_` of shape `(n_features, max_features + 1)`. The first column is always zero."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fc65de7-0c17-456c-933b-72450d46b284",
   "metadata": {},
   "source": [
    "$\\textbf{References}$\n",
    "\n",
    "- Original Algorithm is detailed in the paper [Least Angle Regression](https://www-stat.stanford.edu/~hastie/Papers/LARS/LeastAngle_2002.pdf) by Hastie et al."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "746e8eff-bb52-4826-a3c6-b61379faebb6",
   "metadata": {},
   "source": [
    "### 1.1.9. Orthogonal Matching Pursuit (OMP)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f2378e1-c655-4a1b-82b5-8e053a6dc2bc",
   "metadata": {},
   "source": [
    "[OrthogonalMatchingPursuit](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.OrthogonalMatchingPursuit.html#sklearn.linear_model.OrthogonalMatchingPursuit) and [orthogonal_mp](https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.orthogonal_mp.html#sklearn.linear_model.orthogonal_mp) implement the OMP algorithm for approximating the fit of a linear model with constraints imposed on the number of non-zero coefficients (ie. the \n",
    "$\\ell_0$ pseudo-norm).\n",
    "\n",
    "Being a forward feature selection method like [Least Angle Regression](https://scikit-learn.org/stable/modules/linear_model.html#least-angle-regression), orthogonal matching pursuit can approximate the optimum solution vector with a fixed number of non-zero elements:\n",
    "\n",
    "$$\\arg \\min_w \\lVert y - Xw \\rVert_2^2$$\n",
    "$$\\text{  subject to  } \\lVert w \\rVert_0 \\leq n_{nonzero-coefs}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e3fb62d-0238-461c-989c-cfa9eb11a11c",
   "metadata": {},
   "source": [
    "Alternatively, orthogonal matching pursuit can target a specific error instead of a specific number of non-zero coefficients. This can be expressed as:\n",
    "\n",
    "$$\\arg \\min_w \\lVert w \\rVert_0$$\n",
    "$$\\text{  subject to  } \\lVert y - Xw \\rVert_2^2 \\leq tol$$\n",
    "\n",
    "OMP is based on a greedy algorithm that includes at each step the atom most highly correlated with the current residual. It is similar to the simpler matching pursuit (MP) method, but better in that at each iteration, the residual is recomputed using an orthogonal projection on the space of the previously chosen dicitonary elements."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09fbdb75-1870-4320-8b72-f91ec4d37486",
   "metadata": {},
   "source": [
    "$\\textbf{Example}$\n",
    "- Orthogonal Matching Pursuit - [Sci-kit Link](https://scikit-learn.org/stable/auto_examples/linear_model/plot_omp.html#sphx-glr-auto-examples-linear-model-plot-omp-py) | [Python code](https://github.com/baksho/ml-handson/blob/main/Examples/14_example_plot_omp.py) | [Jupyter Notebook](https://github.com/baksho/ml-handson/blob/main/Examples/14_example_plot_omp.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0af2b491-5932-4682-87d0-4a1ff212aea7",
   "metadata": {},
   "source": [
    "$\\textbf{References}$\n",
    "\n",
    "- [Efficient Implementation of the K-SVD Algorithm\n",
    "using Batch Orthogonal Matching Pursuit](https://www.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf), R. Rubinstein, M. Zibulevsky, M. Elad.\n",
    "- [Matching pursuits with time-frequency dictionaries](https://www.di.ens.fr/~mallat/papiers/MallatPursuit93.pdf), S. G. Mallat, Z. Zhang."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9dc14aa-dacd-4bd6-bac7-5fea1e105bb6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}