Report

Dynamic Programming Tutorial Elaine Chew QMUL: ELE021/ELED021/ELEM021 26 March 2012 Sources • Hillier, F. S. & G. J. Lieberman. Introduction to Operations Research. Chapter 11: Dynamic Programming, 7th, 8th, 9th editions, McGraw-Hill. • Dixon, S. & Widmer, G. (2005). MATCH: A Music Alignment Tool Chest. In Proceedings of the 6th Intl Conf on Music Information Retrieval, London, UK, 492497. • Yang, A., E. Chew & A. Volk (2005). A Dynamic Programming Approach to Adaptive Tatum Assignment for Rhythm Transcription. In Proceedings of the 1st IEEE Intl Wkshop on Multimedia Information Processing and, Irvine, CA, 577-584. Sources • Hillier, F. S. & G. J. Lieberman. Introduction to Operations Research. Chapter 11: Dynamic Programming, 7th, 8th, 9th editions, McGraw-Hill. • Dixon, S. & Widmer, G. (2005). MATCH: A Music Alignment Tool Chest. In Proceedings of the 6th Intl Conf on Music Information Retrieval, London, UK, 492497. • Yang, A., E. Chew & A. Volk (2005). A Dynamic Programming Approach to Adaptive Tatum Assignment for Rhythm Transcription. In Proceedings of the 1st IEEE Intl Wkshop on Multimedia Information Processing and, Irvine, CA, 577-584. Shortest Path Problem • V = set of vertices (or nodes) • E = set of edges (or arcs), including s (source) and t (sink) • C = [cij] = set of arc costs • X = indicator variable for whether arc ij is used • Linear Programming Problem Formulation: Min s.t. Σij cijxij Σi xij = 1 Σj xij = 1 0 ≤ xij ≤ 1 Hogwarts (Shortest Path) Example • Determine which route from entrance to exit has the shortest distance Gringott’s Wizarding Bank G E Quality Quidditch Supplies 7 Entrance to Wizarding 2 World 2 Ollivander’s 5 4 1 3 M 1 C 4 Magical Menagerie R 5 Q 4 O Exit to Charing Cross Road The Leaky Cauldron 7 Algorithm • At iteration i – Objective: find the i-th nearest node to the origin – Input: i-1 nearest node to the origin, shortest path and distance – Candidates for i-th nearest node: nearest unsolved node to one solved – Calculation for i-th nearest node: for each new candidate, add new edge to previously found shortest path to the i-1-th nearest node. Among the new candidates, the node with shortest distance becomes the i-th nearest node. Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection Hogwarts (Shortest Path) Example G 7 2 0 2 5 E 5 4 Q 4 O 1 3 M 1 C 4 7 R Implementation Iteration, i 1 Solved nodes connected to unsolved R Closest connected unsolved node Q Total distance involved 5 i-th nearest node Q Minimum distance 5 Last connection Q Hogwarts (Shortest Path) Example G 7 2 0 2 5 E 5 4 Q 4 O 1 3 M 1 C 4 5 7 R Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 1 R Q 5 Q 5 R 2 Q R C C 6 7 C 6 Q Hogwarts (Shortest Path) Example G 7 2 0 2 5 E 5 4 Q 4 O 1 3 M 5 1 7 C 4 6 R Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 1 R Q 5 Q 5 R 2 Q R C C 6 7 C 6 Q 3 Q C O O 9 9 O 9 Q C Hogwarts (Shortest Path) Example G 7 2 0 2 5 9 E 5 4 Q 4 O 1 3 M 5 1 7 C 4 6 R Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 1 R Q 5 Q 5 R 2 Q R C C 6 7 C 6 Q 3 Q C O O 9 9 O 9 Q C 4 Q C O G M M 12 10 10 M 10 C O Hogwarts (Shortest Path) Example G 7 2 0 2 5 9 E 5 4 1 3 M 10 Q 4 O 5 1 7 C 4 6 R Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 1 R Q 5 Q 5 R 2 Q R C C 6 7 C 6 Q 3 Q C O O 9 9 O 9 Q C 4 Q C O G M M 12 10 10 M 10 C O 5 Q O M G G E 12 11 14 G 11 O Hogwarts (Shortest Path) Example 11 G 7 2 0 2 5 9 E 5 4 1 3 M 10 Q 4 O 5 1 7 C 4 6 R Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 1 R Q 5 Q 5 R 2 Q R C C 6 7 C 6 Q 3 Q C O O 9 9 O 9 Q C 4 Q C O G M M 12 10 10 M 10 C O 5 Q O M G G E 12 11 14 G 11 O Implementation Iteration, i Solved nodes connected to unsolved Closest connected unsolved node Total distance involved i-th nearest node Minimum distance Last connection 5 Q O M G G E 12 11 14 G 11 O 6 O M G E E E 14 14 13 E 13 G Hogwarts (Shortest Path) Example 11 G 7 2 0 2 5 9 13 E 5 4 1 3 M 10 Q 4 O 5 1 7 C 4 6 R Sources • Hillier, F. S. & G. J. Lieberman. Introduction to Operations Research. Chapter 11: Dynamic Programming, 7th, 8th, 9th editions, McGraw-Hill. • Dixon, S. & Widmer, G. (2005). MATCH: A Music Alignment Tool Chest. In Proceedings of the 6th Intl Conf on Music Information Retrieval, London, UK, 492497. • Yang, A., E. Chew & A. Volk (2005). A Dynamic Programming Approach to Adaptive Tatum Assignment for Rhythm Transcription. In Proceedings of the 1st IEEE Intl Wkshop on Multimedia Information Processing and, Irvine, CA, 577-584. Dynamic Time Warping Euclidean Distance (i,j ) Sources • Hillier, F. S. & G. J. Lieberman. Introduction to Operations Research. Chapter 11: Dynamic Programming, 7th, 8th, 9th editions, McGraw-Hill. • Dixon, S. & Widmer, G. (2005). MATCH: A Music Alignment Tool Chest. In Proceedings of the 6th Intl Conf on Music Information Retrieval, London, UK, 492497. • Yang, A., E. Chew & A. Volk (2005). A Dynamic Programming Approach to Adaptive Tatum Assignment for Rhythm Transcription. In Proceedings of the 1st IEEE Intl Wkshop on Multimedia Information Processing and, Irvine, CA, 577-584. Tatum Segmentation • Tatum = smallest perceptual time unit in music Example Results 140 Coarse Manual Segmentation bepthq3 120 son08_3 Tatum 100 80 60 40 0 100 200 300 Beats 400 Segmentation • Example of tatum selection • Input: – Note onset times, O(1,n) = {O1, O2,…, On} • Output: – Segmentation points, S = {S1, S2,…,Sm} – Optimal tatum in each segment Remainder Squared Error p o(1) … 1 … o(j) j j+1 p ERR(.) The error incurred by a tatum assignment, p, for onsets O(i+ 1,k) is given by the remainder squared error (RSE) function: oj oj 1 e(p,i 1,k) , p 2 j 1 p 2 k i 1 where oj (= Oj+1 – Oj) is the inter onset interval (IOI) between onsets j and j+1. ERR(O(i 1,k)) min e(p,i 1,k). p Optimal Segmentation • Define OPT(k) to be the best segmentation (cost) for a given set of onsets O(1,k): OPT(k) min {OPT(i) ERR(O(i 1,k))}, 1i k where ERR(.) returns the error incurred by the best tatum assignment for the set of onsets O(i+1,k). 1 … i i+1 … k