Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:goldm:ch6 [2018/03/26 23:09] – goldm | courses:cs211:winter2018:journals:goldm:ch6 [2018/03/26 23:30] (current) – goldm | ||
|---|---|---|---|
| Line 11: | Line 11: | ||
| This section better begins to explain exactly what dynamic programming is as opposed to just giving a single example of how to do a problem in a specific way. It gets a 6.5/10. | This section better begins to explain exactly what dynamic programming is as opposed to just giving a single example of how to do a problem in a specific way. It gets a 6.5/10. | ||
| + | |||
| + | ===== 6.3: Segmented Least Squares: Multi-way Choices ===== | ||
| + | This section begins by discussing an important distinction about future problems and previous problems. The previous problems dealt with binary choices, either an item belonged in the final solution or it did not. This section deals with the idea that at each step we may have a polynomial number of choices. This is a multi-way choice. It suggests, however, that going from binary to multi-way is a smooth transition. This brings us to the problem the chapter is about, the Segmented Least Squares Problem. This can be seen as finding the appropriate number of lines of best fit needed to approximate the points on a graph and minimize error. This problem is known as change detection. Given a sequence, we want to find certain points where a discrete change takes place. In the context of the aforementioned problem, this is going from one linear approximation to another. In order to solve this problem, we associate a penalty with adding another line to the approximation. Thus, we wish to find a partition with the least downside. We thus wish to optimize the number of segments so that we are not penalized too harshly for making too many partitions, but we still get to greatly reduce the total error associated with the points of the graph being above/below the line(s) of best fit. While we love seeing linear algorithms, due to the complexity of the problem, we end up with a quadratic runtime. This runtime, while slightly higher than we are used to, ends up being practical in the grand scheme of things. | ||
| + | |||
| + | This section kind of dragged on for me. I typically like the specific problem sections less. I give this a 5/10. | ||
