# Optimization Techniques TODO: Break this page out ### Least Squares Least squares is a standard approach to regression analysis (see [wiki](https://en.wikipedia.org/wiki/Least_squares)). We can define the problem as follows: We are given a simple dataset of $n$ points $(x_i, y_i)$, for $i=1,\dots,n$, where $x_i$ is an independent variable and $y_i$ is a dependent variable whose value is found via observation. We model this relationship via a function $f(x, \beta)$, where $\beta$ holds $m$ adjustable parameters (i.e. $\beta$ is an $m$ dimensional vector): $f: x \rightarrow y$ The goal is to find the values of $\beta$ that best model the *true relationship* between $x$ and $y$. We state that the fit of a model to it's data point is measured by it's *residual*, defined as the difference between the actual and predicted value: $r_i = y_i - f(x_i, \beta)$ The least squares method finds the optimal parameter values by minimizing the sum of the squared residuals: $S = \sum_{i=1}^{n} r_i^2$ This is achieved via setting the [Gradient](Gradient.md) to 0: $\frac{\partial S}{\partial \beta_j} = 2 \sum_{i=1}^n r_i \frac{\partial f(x_i, \beta)}{\partial \beta_i} = 0$ And because $r_i = y_i - f(x_i, \beta)$, our equation becomes: $\frac{\partial S}{\partial \beta_j} = 2 \sum_{i=1}^n r_i \frac{\partial \big( y_i - f(x_i, \beta) \big)}{\partial \beta_i} = 2 \sum_{i=1}^n r_i \Big( \frac{\partial y_i}{\partial \beta_i} - \frac{\partial f(x_i, \beta)}{\partial \beta_i} \Big) = - 2 \sum_{i=1}^n r_i \Big( \frac{\partial f(x_i, \beta)}{\partial \beta_i} \Big)= 0$ Where $\frac{\partial y_i}{\partial \beta_i}$ went to $0$ because $y_i$ are fixed observations, hence constant. --- Date: 20210521 Links to: [Mathematics MOC](Mathematics%20MOC.md) [003-Data-Science-MOC](003-Data-Science-MOC.md) References: * [Least Squares - Fitting a line to data](https://www.youtube.com/watch?v=PaFPbb66DxQ)