Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:boyese:chapter6 [2018/03/27 22:59] – [Section 6.3: Segmented Least Squares: Multi-way Choices] boyese | courses:cs211:winter2018:journals:boyese:chapter6 [2018/03/27 23:00] (current) – [Section 6.3: Segmented Least Squares: Multi-way Choices] boyese |
|---|
| In the problem we consider here, the recurrence will involve what might be called "multi-way choices": at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution. This problem involves finding a line of best fit for a collection of points on a graph. This process is used frequently in statistics and called regression, but in this case the points do not fall along a straight line. Any single line through the points on a polynomial graph would have a terrible error; but if we use two lines, we could achieve quite a small error. So we could try formulating a new problem as follows: Rather than seek a single line of best fit, we are allowed to pass an arbitrary set of lines through the points, and we seek a set of lines that minimizes the error. We need a problem formulation that requires us to fit the points well, using as few lines as possible. We now formulate a problem--the Segmented Least Squares Problem--that captures these issues quite cleanly. | In the problem we consider here, the recurrence will involve what might be called "multi-way choices": at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution. This problem involves finding a line of best fit for a collection of points on a graph. This process is used frequently in statistics and called regression, but in this case the points do not fall along a straight line. Any single line through the points on a polynomial graph would have a terrible error; but if we use two lines, we could achieve quite a small error. So we could try formulating a new problem as follows: Rather than seek a single line of best fit, we are allowed to pass an arbitrary set of lines through the points, and we seek a set of lines that minimizes the error. We need a problem formulation that requires us to fit the points well, using as few lines as possible. We now formulate a problem--the Segmented Least Squares Problem--that captures these issues quite cleanly. |
| |
| Suppose we let OPT(i) denote the optimum solution for the points p<sub>1</sub>, ..., p<sub>i</sub> and we let e<sub>i, j</sub> denote the minimum error of any line with respect to p<sub>i</sub>, p<sub>i + 1</sub>, ..., <sub>j</sub>. Then our observation above says that if the last segment of the optimal partition is p<sub>i</sub>, ..., p<sub>n</sub>, then the value of the optimal solution is OPT(n) = e<sub>i, n</sub> + C + OPT(i - 1). The algorithm is as follows: | Suppose we let OPT(i) denote the optimum solution for the points p<sub>1</sub>, ..., p<sub>i</sub> and we let e<sub>i, j</sub> denote the minimum error of any line with respect to p<sub>i</sub>, p<sub>i + 1</sub>, ..., p<sub>j</sub>. Then our observation above says that if the last segment of the optimal partition is p<sub>i</sub>, ..., p<sub>n</sub>, then the value of the optimal solution is OPT(n) = e<sub>i, n</sub> + C + OPT(i - 1). The algorithm is as follows: |
| |
| <code> | <code> |
