Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:thetfordt:chapter6 [2018/03/26 18:17] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter6 [2018/03/26 18:32] (current) – thetfordt
@@ Line 26: / Line 26: @@
 ===== Section 6.3 - Segmented Least Squares: Multi-way Choices =====
+In the previous sections, we opened the logic of solving the problems with a binary choice: either the final job lied in the solution or it did not. But this is not always the case. In this section, we will tackle a multi-way choice problem.
+The problem we will be examining has to do with points on an x-y plane. We know how to minimize the sum of squares with a set of points by creating a best-fit line. But if we could have multiple lines? And what if we wanted to minimize both the sums of squares (have an accurate best-fit line), but also minimize the number of lines used in order to minimize the sums of squares.
+Say that we are given a set of points on an x-y plane. We need to create a penalty of partitioning the x-values (to create a new line). We see that the penalty of a partition is
+(i) the number of segments into which we partition P, times a fixed given multiplier C>0
+(ii) For each segment, the error value of the optimal line through that segment.
+Our goal here is to find a partition such that we minimize our penalty. The section walks through a few subproofs before laying out the algorithm itself. First, we call e(i,j) the minimum error of any line with respect to points p_i,...,p_j (points ordered by increasing x-value). The book lays out the fact that if the last segment of the optimal partition is p_i,...,p_n, then the value of the optimal solution is Opt(n) = e(i,n) + C + Opt(i-1). This makes sense to me in an intuitive nature. Additionally, we define Opt(j) on the points p_1,...,p_j to be min ((for 1 <= i <= j) e(i,j) + C + Opt(i-1)). Using these facts, we are able to design an algorithm which directly stems from the logic laid before us.
+The algorithm defines an array M[0,...,n], and sets M[0] = 0. ANd for all pairs with i<=j, we compute the least squares error e(i,j) for the segment p_i,...,p_j. And then for j = 1,2,...,n, we use recurrence of the formula laid out in the previous paragraph to compute M[j]. And then we just return M[n]. In order to determine the runtime of the algorithm as a whole, we note that it takes O(n^2) time to examine all of the pairs. But even further, it takes O(n^3) time to compute all of the e(i,j) values. The second for-loop takes O(n^2) time, yielding a total algorithm runtime of O(n^3).
+I was absent from class during the coverage of this material, so this section was a little more difficult for me to digest. Altough, I found the book's explanations fairly straight-forward. I would rate the readability of this section at 7/10.