jazzparser.formalisms.music_halfspan.evaluation

1 """Tonal space path evaluation functions. 2 3 """ 4 """ 5 ============================== License ======================================== 6 Copyright (C) 2008, 2010-12 University of Edinburgh, Mark Granroth-Wilding 7 8 This file is part of The Jazz Parser. 9 10 The Jazz Parser is free software: you can redistribute it and/or modify 11 it under the terms of the GNU General Public License as published by 12 the Free Software Foundation, either version 3 of the License, or 13 (at your option) any later version. 14 15 The Jazz Parser is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with The Jazz Parser. If not, see <http://www.gnu.org/licenses/>. 22 23 ============================ End license ====================================== 24 25 """ 26 __author__ = "Mark Granroth-Wilding <mark.granroth-wilding@ed.ac.uk>" 27 28 from jazzparser.utils.base import group_pairs 29

30 -def _subst_type(point1, point2):

31 root = point1[0] != point2[0] 32 function = point1[1] != point2[1] 33 if root and function: 34 return "both" 35 elif root: 36 return "root" 37 elif function: 38 return "fun" 39 else: 40 return "match"

41

42 -def _subst_cost(point1, point2):

43 return { 44 "both" : 2, 45 "root" : 1, 46 "fun" : 1, 47 "match": 0 48 }[_subst_type(point1, point2)]

49

50 -def _subst_cost_float(point1, point2):

51 """ 52 Substitution cost, same as _subst_cost, but returns a value between 0 53 and 1. 54 55 """ 56 return float(_subst_cost(point1,point2))/2

57

58 -def _steps_list(seq):

59 """ 60 Given a list of (coordinate,function) pairs, produces a similar list 61 that represents the steps between each point in the path and its previous 62 point, maintaining the original functions. 63 64 The first point yields the step 65 from the origin, ignoring its enharmonic block (in other words, the 66 step from (0,0) within its enharmonic block). 67 68 This means that effectively we don't care what enharmonic block the 69 path lies in, only the relative points along the path. 70 71 """ 72 def _minus(c0, c1): 73 return (c0[0]-c1[0], c0[1]-c1[1])

74 75 # Get the functions out for later 76 coords,funs = zip(*seq) 77 steps = [coords[0]] + [(_minus(c1,c0)) for c0,c1 in group_pairs(coords)] 78 # Put the functions back in for the result 79 return zip(steps, funs) 80

81 -def _lf_to_coord_funs(sem):

82 """ 83 Gets a list of (coordinate,function) pairs from a logical form. 84 85 """ 86 from jazzparser.formalisms.music_halfspan.semantics import \ 87 list_lf_to_coordinates, list_lf_to_functions 88 # Convert the LF to a list of coordinates 89 coords,__ = zip(*list_lf_to_coordinates(sem)) 90 # And to a list of functions 91 funs,__ = zip(*list_lf_to_functions(sem)) 92 # Put them together into (coord,fun) pairs 93 return zip(coords,funs)

94

95 -def tonal_space_distance(sem1, sem2):

96 """ 97 Computes the edit distance between the tonal space paths of two logical 98 forms, using a suitable scoring. This uses a cost of 2 for deletions and 99 insertions and scores 1 for a substitution that gets either 100 the step or function right, but not both. The result is then 101 divided by 2 (meaning that effectively all costs are 1 and a 0.5 102 cost is given to half-right substitutions). 103 104 The alignment is not between the tonal space points themselves, but 105 between the vectors between each pair of points (that is the points 106 relative to the previous point). This means that a path won't be 107 penalised if part of it is translated by a constant vector, except at 108 the point where it goes wrong. 109 110 """ 111 from jazzparser.utils.distance import levenshtein_distance 112 # Get a list of (coord,fun) pairs for the logical forms 113 seq1 = _lf_to_coord_funs(sem1) 114 seq2 = _lf_to_coord_funs(sem2) 115 # Produce a version of the paths made up of steps and functions, 116 # rather than points and functions 117 steps1 = _steps_list(seq1) 118 steps2 = _steps_list(seq2) 119 120 edit_dist = levenshtein_distance( 121 steps1, 122 steps2, 123 delins_cost=2, 124 subst_cost_fun=_subst_cost) 125 return float(edit_dist) / 2.0

126

127 -def tonal_space_alignment_costs(sem1, sem2):

128 """ 129 Performs the same algorithm as tonal_space_distance, but instead 130 of returning the score returns the counts of deletions, 131 insertions, root (only) substitutions, function (only) 132 substitutions, full substitutions and alignments. 133 134 """ 135 from jazzparser.utils.distance import levenshtein_distance_with_pointers 136 # Get a list of (coord,fun) pairs for the logical forms 137 seq1 = _lf_to_coord_funs(sem1) 138 seq2 = _lf_to_coord_funs(sem2) 139 # Produce a version of the paths made up of steps and functions, 140 # rather than points and functions 141 steps1 = _steps_list(seq1) 142 steps2 = _steps_list(seq2) 143 144 dists,pointers = levenshtein_distance_with_pointers( 145 steps1, 146 steps2, 147 delins_cost=2, 148 subst_cost_fun=_subst_cost) 149 # We now have the matrix of costs and the pointers that generated 150 # those costs. 151 # Trace back to find out what costs were incurred in the optimal 152 # alignment 153 insertions = 0 154 deletions = 0 155 function_subs = 0 156 root_subs = 0 157 full_subs = 0 158 alignments = 0 159 # Start at the top right corner 160 i,j = (len(dists)-1), (len(dists[0])-1) 161 while not i == j == 0: 162 if pointers[i][j] == "I": 163 insertions += 1 164 j -= 1 165 elif pointers[i][j] == "D": 166 deletions += 1 167 i -= 1 168 else: 169 # Substitution: find out what kind 170 step1 = steps1[i-1] 171 step2 = steps2[j-1] 172 subst_type = _subst_type(step1, step2) 173 if subst_type == "both": 174 full_subs += 1 175 elif subst_type == "fun": 176 function_subs += 1 177 elif subst_type == "root": 178 root_subs += 1 179 else: 180 alignments += 1 181 j -= 1 182 i -= 1 183 184 return { 185 'deletions' : deletions, 186 'insertions' : insertions, 187 'root_subs' : root_subs, 188 'function_subs' : function_subs, 189 'full_subs' : full_subs, 190 'substitutions' : root_subs+function_subs+full_subs, 191 'alignments' : alignments, 192 'steps1' : steps1, 193 'steps2' : steps2, 194 }

195

196 -def tonal_space_alignment(sem1, sem2, distance=False):

197 """ 198 Performs the same algorithm as L{tonal_space_distance} and 199 L{tonal_space_alignment_costs}, but returns a list of the operations 200 that produce the optimal alignment: "I" - insertion; "D" - deletion; 201 "A" - alignment; "S" - full substitution; or anything else beginning with 202 "S" to indicate a partial substitution. 203 204 Returns the operation list and the two sequences that were compared. 205 If distance=True, also includes the distance metric. Not included by 206 default for backward compatibility. 207 208 """ 209 from jazzparser.utils.distance import levenshtein_distance_with_pointers 210 # Get a list of (coord,fun) pairs for the logical forms 211 seq1 = _lf_to_coord_funs(sem1) 212 seq2 = _lf_to_coord_funs(sem2) 213 # Produce a version of the paths made up of steps and functions, 214 # rather than points and functions 215 steps1 = _steps_list(seq1) 216 steps2 = _steps_list(seq2) 217 218 dists,pointers = levenshtein_distance_with_pointers( 219 steps1, 220 steps2, 221 delins_cost=2, 222 subst_cost_fun=_subst_cost) 223 224 # We now have the matrix of costs and the pointers that generated 225 # those costs. 226 # Trace back to find out what produces the optimal alignment 227 # Start at the top right corner 228 i,j = (len(dists)-1), (len(dists[0])-1) 229 oplist = [] 230 while not i == j == 0: 231 if pointers[i][j] == "I": 232 oplist.append("I") 233 j -= 1 234 elif pointers[i][j] == "D": 235 oplist.append("D") 236 i -= 1 237 else: 238 # Substitution: find out what kind 239 step1 = steps1[i-1] 240 step2 = steps2[j-1] 241 subst_type = _subst_type(step1, step2) 242 if subst_type == "both": 243 oplist.append("S") 244 elif subst_type == "fun": 245 oplist.append("Sf") 246 elif subst_type == "root": 247 oplist.append("Sr") 248 else: 249 oplist.append("A") 250 j -= 1 251 i -= 1 252 oplist = list(reversed(oplist)) 253 254 if distance: 255 dist = float(dists[-1][-1]) / 2.0 256 return oplist,steps1,steps2,dist 257 else: 258 return oplist,steps1,steps2

259

260 -def tonal_space_align(sem1, sem2):

261 """ 262 Like the other alignment functions, but returns the list of aligned 263 pairs. 264 265 """ 266 from jazzparser.utils.distance import align 267 # Get a list of (coord,fun) pairs for the logical forms 268 seq1 = _lf_to_coord_funs(sem1) 269 seq2 = _lf_to_coord_funs(sem2) 270 # Produce a version of the paths made up of steps and functions, 271 # rather than points and functions 272 steps1 = _steps_list(seq1) 273 steps2 = _steps_list(seq2) 274 275 pairs = align(steps1, steps2, delins_cost=2, subst_cost=_subst_cost) 276 return pairs

277

278 -def tonal_space_precision_recall(sem, gold_sem):

279 """ 280 Calculates the precision and recall and f-score of the optimal alignment 281 between the sequence and the gold standard sequence. 282 283 """ 284 costs = tonal_space_alignment_costs(sem, gold_sem) 285 num_steps = len(costs['steps1']) 286 num_gold_steps = len(costs['steps2']) 287 288 # Work out the positive score for the alignment 289 align_score = float(costs["alignments"]) + \ 290 float(costs["root_subs"]+costs["function_subs"]) / 2.0 291 292 # Compute precision and recall to get f-score 293 precision = align_score / num_steps 294 recall = align_score / num_gold_steps 295 f_score = 2*precision*recall / (precision+recall) 296 return precision,recall,f_score

297

298 -def tonal_space_f_score(sem, gold_sem):

299 """ 300 Calculates an f-score for the optimal alignment between the sequence and 301 the gold standard sequence. 302 303 """ 304 return tonal_space_precision_recall(sem, gold_sem)[2]

305

306 -def tonal_space_alignment_score(seq1, seq2):

307 """ 308 Assigns a score to the optimal alignment between the two logical forms. 309 310 Think of this as essentially a count of alignments in the optimal 311 alignment. In fact, a pair of points may be partly aligned, in which 312 case they contribute something to this score between 0 and 1. 313 314 """ 315 costs = tonal_space_alignment_costs(seq1, seq2) 316 return float(costs["alignments"]) + float(costs["root_subs"]+costs["function_subs"])/2

317

318 -def tonal_space_length(sem):

319 """ 320 Length of the tonal space path represented by the given logical form. 321 322 This could be more efficient, but at the moment only gets used in places 323 where it doesn't matter much, so I might as well keep it simple. 324 325 """ 326 from jazzparser.formalisms.music_halfspan.semantics import Semantics 327 if isinstance(sem, Semantics): 328 sem = sem.lf 329 # Use our standard function to get a tonal space path for the sems 330 seq = _lf_to_coord_funs(sem) 331 return len(seq)

332 333

334 -def tonal_space_local_distance(sem1, sem2):

335 """ 336 Like L{tonal_space_distance}, but uses local alignment of seq2 within 337 seq1. 338 339 """ 340 from jazzparser.utils.distance import local_levenshtein_distance 341 # Get a list of (coord,fun) pairs for the logical forms 342 seq1 = _lf_to_coord_funs(sem1) 343 seq2 = _lf_to_coord_funs(sem2) 344 # Produce a version of the paths made up of steps and functions, 345 # rather than points and functions 346 steps1 = _steps_list(seq1) 347 steps2 = _steps_list(seq2) 348 349 dists,pointers = local_levenshtein_distance( 350 steps1, 351 steps2, 352 delins_cost=2, 353 subst_cost_fun=_subst_cost) 354 return float(dists[-1][-1]) / 2.0

355

356 -def tonal_space_local_alignment(sem1, sem2):

357 """ 358 Like L{tonal_space_alignment}, but uses local alignment of seq2 within seq1. 359 360 Also returns the distance metric (like L{tonal_space_local_distance}. 361 362 """ 363 from jazzparser.utils.distance import local_levenshtein_distance 364 # Get a list of (coord,fun) pairs for the logical forms 365 seq1 = _lf_to_coord_funs(sem1) 366 seq2 = _lf_to_coord_funs(sem2) 367 # Produce a version of the paths made up of steps and functions, 368 # rather than points and functions 369 steps1 = _steps_list(seq1) 370 steps2 = _steps_list(seq2) 371 372 dists,pointers = local_levenshtein_distance( 373 steps1, 374 steps2, 375 delins_cost=2, 376 subst_cost_fun=_subst_cost) 377 378 # We now have the matrix of costs and the pointers that generated 379 # those costs. 380 # Trace back to find out what produces the optimal alignment 381 # Start at the top right corner 382 i,j = (len(dists)-1), (len(dists[0])-1) 383 oplist = [] 384 while not i == j == 0: 385 if pointers[i][j] == "I": 386 oplist.append("I") 387 j -= 1 388 elif pointers[i][j] == "D": 389 oplist.append("D") 390 i -= 1 391 elif pointers[i][j] == ".": 392 oplist.append(".") 393 i -= 1 394 else: 395 # Substitution: find out what kind 396 step1 = steps1[i-1] 397 step2 = steps2[j-1] 398 subst_type = _subst_type(step1, step2) 399 if subst_type == "both": 400 oplist.append("S") 401 elif subst_type == "fun": 402 oplist.append("Sf") 403 elif subst_type == "root": 404 oplist.append("Sr") 405 else: 406 oplist.append("A") 407 j -= 1 408 i -= 1 409 410 oplist = list(reversed(oplist)) 411 distance = float(dists[-1][-1]) / 2.0 412 return oplist, steps1, steps2, distance

413

414 -def arrange_alignment(steps1, steps2, ops):

415 """ 416 Arrange the steps of an alignment for printing in aligned rows. 417 418 """ 419 steps1 = iter(steps1) 420 steps2 = iter(steps2) 421 alignments = [] 422 423 for op in ops: 424 if op == "I": 425 left = "" 426 right = str(steps2.next()) 427 elif op in ["D", "."]: 428 left = steps1.next() 429 right = "" 430 elif op == "A" or op.startswith("S"): 431 left = steps1.next() 432 right = steps2.next() 433 cells = [str(left),str(right),str(op)] 434 width = max(len(txt) for txt in cells) 435 cells = [cell.ljust(width) for cell in cells] 436 alignments.append(cells) 437 438 return alignments

439

Source Code for Module jazzparser.formalisms.music_halfspan.evaluation