jazzparser.formalisms.music_halfspan.semantics.distance

1 """Semantic distance metrics. 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.options import ModuleOption, choose_from_list 29 from jazzparser.formalisms.base.semantics.distance import DistanceMetric, \ 30 FScoreMetric 31 from jazzparser.formalisms.music_halfspan.evaluation import tonal_space_f_score, \ 32 tonal_space_alignment_score, tonal_space_align, \ 33 arrange_alignment, tonal_space_distance, \ 34 tonal_space_length 35

36 -class TonalSpaceEditDistance(FScoreMetric):

37 """ 38 Original tonal space distance metric computed as the edit distance of 39 the step vectors and functions of the path through the tonal space 40 implied by the semantics. 41 42 """ 43 OPTIONS = [ 44 ModuleOption('output', filter=choose_from_list( 45 ['f','precision','recall','inversef','dist']), 46 usage="output=O, where O is one of 'f', 'precision', "\ 47 "'recall', 'inversef', 'dist'", 48 default='dist', 49 help_text="Select what metric to output. Choose recall "\ 50 "or precision for asymmetric metrics. F-score ('f') "\ 51 "combines these two. This is inverted ('inversef') "\ 52 "to get a distance, rather than similarity. "\ 53 "Alternatively, use the edit distance of the alignment "\ 54 "('dist', default)"), 55 ] 56 name = "tsed" 57

58 - def fscore_match(self, sem1, sem2):

59 if sem1 is None or sem2 is None: 60 alignment_score = 0.0 61 else: 62 alignment_score = tonal_space_alignment_score(sem1.lf, sem2.lf) 63 64 if sem1 is None: 65 len1 = 0.0 66 else: 67 len1 = tonal_space_length(sem1) 68 if sem2 is None: 69 len2 = 0.0 70 else: 71 len2 = tonal_space_length(sem2) 72 return alignment_score,len1,len2

73

74 - def _get_identifier(self):

75 ident = { 76 'f' : 'f-score', 77 'precision' : 'precision', 78 'recall' : 'recall', 79 'inversef' : 'inverse f-score', 80 'dist' : 'edit distance', 81 } 82 return "tsed %s" % ident[self.options['output']]

83 identifier = property(_get_identifier) 84

85 - def distance(self, sem1, sem2):

86 # Handle the extra 'dist' case 87 if self.options['output'] == 'dist': 88 # If one input is empty, we consider all points to have been deleted 89 if sem1 is None: 90 return tonal_space_length(sem2) 91 elif sem2 is None: 92 return tonal_space_length(sem1) 93 94 # Compute the score using our standard TS distance computation 95 # This is based on the alignment score of the optimal alignment 96 # of the two sequences 97 return tonal_space_distance(sem1.lf, sem2.lf) 98 else: 99 # Otherwise the superclass takes care of everything 100 return super(TonalSpaceEditDistance, self).distance(sem1, sem2)

101

102 - def print_computation(self, sem1, sem2):

103 """ 104 Shows the optimal alignment of the paths that the score comes from. 105 106 @see: jazzparser.formalisms.music_halfspan.semantics.distance.DistanceMetric.print_computation 107 108 """ 109 pairs = tonal_space_align(sem1.lf, sem2.lf) 110 return "\n".join(["%s %s" % pair for pair in pairs])

111

112 - def total_distance(self, input_pairs):

113 """ Handle the 'dist' output specially (just sum up distances). """ 114 if self.options['output'] == 'dist': 115 # Do the normal (non-f-score) metric thing of summing up all vals 116 return DistanceMetric.total_distance(self, input_pairs) 117 else: 118 return FScoreMetric.total_distance(self, input_pairs)

119

120 - def format_distance(self, dist):

121 if self.options['output'] == 'dist': 122 return "%f" % dist 123 else: 124 return FScoreMetric.format_distance(self, dist)

125 126

127 -def _cadence_type(tree):

128 # The grammar currently ensures that only one cadence type is used 129 # throughout a specific cadence. If this changes, we'll want to 130 # redefine this metric 131 if len(tree.root) == 0: 132 # Root is a leaf: no cadence 133 return "NA" 134 else: 135 # Pick the first label we come across 136 label = tree.root[0].label 137 if label == "leftonto": 138 return "perfect" 139 elif label == "rightonto": 140 return "plagal" 141 else: 142 raise ValueError, "unknown cadence type with node label "\ 143 "'%s' in the dependency graph" % label

144

145 -class LargestCommonEmbeddedSubtrees(FScoreMetric):

146 """ 147 Tonal space distance metric computed as the size of the largest subtree 148 that can be embedded in the dependency graphs of two logical forms. This 149 is done separately for each alignment of cadences in the two logical 150 forms and the global optimum is used. 151 152 """ 153 OPTIONS = FScoreMetric.OPTIONS + [ 154 ModuleOption('res_score', filter=int, 155 usage="res_score=R, where R is an integer", 156 default=2, 157 help_text="Score to give to matching resolutions. 1 "\ 158 "is the score given to a matching node in the "\ 159 "dependency tree. The default (2) gives more "\ 160 "weight to matching resolutions that tree nodes. "\ 161 "Special value -1 assigns a weight equal to the size "\ 162 "of the common dependency tree + 1"), 163 ] 164 name = "lces" 165

166 - def _get_identifier(self):

167 ident = { 168 'f' : 'f-score', 169 'precision' : 'precision', 170 'recall' : 'recall', 171 'inversef' : 'inverse f-score', 172 } 173 return "dependency tree %s" % ident[self.options['output']]

174 identifier = property(_get_identifier) 175

176 - def fscore_match(self, sem1, sem2):

177 """ 178 The core computation of the distance metric. Takes care of the tree 179 comparison and cadence alignment and return the vital statistics. 180 181 """ 182 from jazzparser.formalisms.music_halfspan.harmstruct import \ 183 semantics_to_dependency_trees 184 from jazzparser.misc.tree.lces import lces_size 185 from jazzparser.utils.distance import align 186 187 res_score = self.options['res_score'] 188 189 # Get dependency graphs for the two logical forms 190 if sem1 is None: 191 trees1 = [] 192 else: 193 trees1 = semantics_to_dependency_trees(sem1) 194 if sem2 is None: 195 trees2 = [] 196 else: 197 trees2 = semantics_to_dependency_trees(sem2) 198 199 if sem1 is None or sem2 is None: 200 # Empty input: give zero score to everything 201 alignment_score = 0.0 202 alignment = [] 203 transpose = None 204 else: 205 # Try each possible transposition of the second tree to make this 206 # metric key independent 207 distances = [] 208 for x_trans in range(4): 209 for y_trans in range(3): 210 def _align(tree1, tree2): 211 # Transpose the label in the second tree 212 label2 = ((tree2.root.label[0] + x_trans) % 4, 213 (tree2.root.label[1] + y_trans) % 3) 214 # Check the root to find out whether they have the same resolution 215 same_res = tree1.root.label == label2 216 # Find out what cadence type each is 217 same_cad = _cadence_type(tree1) == _cadence_type(tree2) 218 if same_cad: 219 # Compare the structure of the cadences 220 tree_similarity = lces_size(tree1, tree2) 221 else: 222 tree_similarity = 0 223 224 # Work out how much score to give a matching resolution 225 if res_score == -1: 226 res_match = tree_similarity + 1 227 else: 228 res_match = res_score 229 return - tree_similarity - (res_match if same_res else 0)

230 231 aligned,dist = align(trees1, trees2, delins_cost=0, 232 subst_cost=_align, 233 dist=True) 234 distances.append((dist,aligned,(x_trans,y_trans))) 235 236 alignment_score,alignment,transpose = min(distances, 237 key=lambda x:x[0]) 238 alignment_score = -float(alignment_score) 239 240 def _max_score(trees): 241 """ 242 Get the maximum possible score that could be assigned to a match 243 with this tree set. 244 245 """ 246 score = 0 247 for tree in trees: 248 # Do the same things as _align (below), but max possible score 249 # Maximum similarity is just the size of the tree 250 tree_sim = len(tree) 251 if res_score == -1: 252 res_match = tree_sim + 1 253 else: 254 res_match = res_score 255 # Assume the same resolution and cadence type 256 score += tree_sim + res_match 257 return score

258 max_score1 = _max_score(trees1) 259 max_score2 = _max_score(trees2) 260 261 return alignment_score, max_score1, max_score2, alignment, transpose 262

263 - def print_computation(self, sem1, sem2):

264 from jazzparser.misc.tree.lces import lces 265 from cStringIO import StringIO 266 267 stats = self.fscore_match(sem1, sem2) 268 trans = stats[4] 269 buf = StringIO() 270 271 print >>buf, "LF1: %s" % sem1 272 print >>buf, "LF2: %s" % sem2 273 print >>buf, "LF2 transposed by (%d,%d)\n" % trans 274 print >>buf, "Maximal cadence alignment:" 275 # Go through all the aligned cadences and show the components of the 276 # scores 277 for sem1cad, sem2cad in stats[3]: 278 if sem1cad is None: 279 print >>buf, "1: deleted" 280 else: 281 print >>buf, "1: %s" % sem1cad 282 if sem2cad is None: 283 print >>buf, "2: deleted" 284 else: 285 print >>buf, "2: %s" % sem2cad 286 if sem1cad is not None and sem2cad is not None: 287 # Cadences were aligned: explain how 288 print >>buf, "Cadence types: %s %s" % (_cadence_type(sem1cad), 289 _cadence_type(sem2cad)) 290 root2 = sem2cad.root.label 291 root2 = ((root2[0]+trans[0])%4, (root2[1]+trans[1])%3) 292 print >>buf, "Resolutions: %s %s" % (sem1cad.root.label, root2) 293 common = lces(sem1cad, sem2cad) 294 print >>buf, "Shared structure: %s (size %d)" % (common, len(common)-1) 295 print >>buf 296 return buf.getvalue()

297

298 -class OptimizedDependencyRecovery(FScoreMetric):

299 """ 300 Aligns the two dependency graphs in the way that optimizes their 301 dependency recovery and reports that dependency recovery. This gives 302 a metric that can be used when the alignment between the graphs is not 303 known, such as when parsing MIDI. 304 305 """ 306 name = "optdeprec" 307

308 - def _get_identifier(self):

309 ident = { 310 'f' : 'f-score', 311 'precision' : 'precision', 312 'recall' : 'recall', 313 'inversef' : 'inverse f-score', 314 } 315 return "dependency alignment %s" % ident[self.options['output']]

316 identifier = property(_get_identifier) 317

318 - def fscore_match(self, sem1, sem2):

319 from jazzparser.formalisms.music_halfspan.harmstruct import \ 320 semantics_to_dependency_graph 321 from jazzparser.data.dependencies import optimal_node_alignment, \ 322 alignment_to_graph 323 from jazzparser.formalisms.music_halfspan.semantics import \ 324 EnharmonicCoordinate 325 326 if sem1 is None: 327 max_score1 = 0.0 328 else: 329 graph1,timings1 = semantics_to_dependency_graph(sem1) 330 max_score1 = float(len(graph1)) 331 332 if sem2 is None: 333 max_score2 = 0.0 334 else: 335 graph2,timings2 = semantics_to_dependency_graph(sem2) 336 max_score2 = float(len(graph2)) 337 338 if sem1 is None or sem2 is None: 339 # Empty input: give zero score to everything 340 alignment_score = 0.0 341 alignment = [] 342 transpose = None 343 else: 344 graph1,timings1 = semantics_to_dependency_graph(sem1) 345 graph2,timings2 = semantics_to_dependency_graph(sem2) 346 347 graphs = [] 348 # Try all possible transpositions and assume the best 349 for transx in range(4): 350 for transy in range(3): 351 def _label_compare(label1, label2): 352 if isinstance(label1, EnharmonicCoordinate) and \ 353 isinstance(label2, EnharmonicCoordinate): 354 coord1 = label1.zero_coord 355 x2,y2 = label2.zero_coord 356 return coord1 == ((x2+transx)%4, (y2+transy)%3) 357 else: 358 return label1 == label2

359 360 # Find the alignment of the nodes that matches most dependencies 361 alignment = optimal_node_alignment(graph1, graph2, label_compare=_label_compare) 362 # Get the common dependency graph 363 graph, node_map1, node_map2 = alignment_to_graph(alignment, 364 graph1, graph2, label_compare=_label_compare) 365 366 graphs.append(graph) 367 368 # Score on the basis of the shared dependencies 369 alignment_score,graph = max([(len(graph),graph) for graph in graphs], key=lambda x:x[0]) 370 371 return alignment_score,max_score1,max_score2

372

373 -class DependencyRecovery(FScoreMetric):

374 """ 375 Exact dependency recovery metric. Only matches two nodes to each other 376 if they have the same time attached to them. This is for use with results 377 where we know the input is the same as that over which the gold standard 378 is defined. 379 380 For example, evaluating chord sequence parsing against the 381 corpus we know this. It won't work, however, evaluating midi parsing 382 against the chord corpus. 383 384 It is also not pitch-independent, since it's only useful where the input 385 over which the result was produced is the same anyway. 386 387 """ 388 name = "deprec" 389

390 - def _get_identifier(self):

391 ident = { 392 'f' : 'f-score', 393 'precision' : 'precision', 394 'recall' : 'recall', 395 'inversef' : 'inverse f-score', 396 } 397 return "dependency recovery %s" % ident[self.options['output']]

398 identifier = property(_get_identifier) 399

400 - def fscore_match(self, sem1, sem2):

401 from jazzparser.formalisms.music_halfspan.harmstruct import \ 402 semantics_to_dependency_graph 403 from jazzparser.data.dependencies import optimal_node_alignment, \ 404 alignment_to_graph 405 from jazzparser.formalisms.music_halfspan.semantics import \ 406 EnharmonicCoordinate 407 408 if sem1 is None: 409 max_score1 = 0.0 410 else: 411 graph1,timings1 = semantics_to_dependency_graph(sem1) 412 max_score1 = float(len(graph1)) 413 414 if sem2 is None: 415 max_score2 = 0.0 416 else: 417 graph2,timings2 = semantics_to_dependency_graph(sem2) 418 max_score2 = float(len(graph2)) 419 420 if sem1 is None or sem2 is None: 421 # Empty input: give zero score to everything 422 alignment_score = 0.0 423 alignment = [] 424 transpose = None 425 else: 426 graph1,timings1 = semantics_to_dependency_graph(sem1) 427 graph2,timings2 = semantics_to_dependency_graph(sem2) 428 429 node_pairs = [] 430 # Always align the root nodes to each other 431 node_pairs.append((min(graph1.nodes), min(graph2.nodes))) 432 433 # Align nodes that occur at the same time 434 time_nodes1 = dict([(time,node) for (node,time) in timings1.items()]) 435 for node2,time in sorted(timings2.items(), key=lambda x:x[1]): 436 if time in time_nodes1: 437 node_pairs.append((time_nodes1[time], node2)) 438 439 def _label_compare(label1, label2): 440 if isinstance(label1, EnharmonicCoordinate) and \ 441 isinstance(label2, EnharmonicCoordinate): 442 return label1.zero_coord == label2.zero_coord 443 else: 444 return label1 == label2

445 # Get the graph of shared dependencies that results from aligning 446 # simultaneous nodes 447 graph,node_map1,node_map2 = alignment_to_graph(node_pairs, 448 graph1, graph2, label_compare=_label_compare) 449 450 # Score on the basis of the shared dependencies 451 alignment_score = len(graph) 452 453 return alignment_score,max_score1,max_score2

454

455 -class RandomDistance(DistanceMetric):

456 """ 457 Returns a distance by picking a random number. This is useful for 458 establishing a random baseline on evaluations. 459 Obviously it won't be the same for two calls on the same inputs. 460 461 """ 462 OPTIONS = [] 463 name = "rand" 464

465 - def distance(self, sem1, sem2):

466 import random 467 return random.random()

468

469 -class DependencyGraphSize(DistanceMetric):

470 """ 471 This is a baseline metric that does nothing clever. It's designed to 472 show how well a system could do just by comparing the lengths of the 473 two analyses in terms of the number of dependencies in them. 474 We'd hope it wouldn't do very well, but it's an important 475 baseline to try. 476 477 The distance is the inverse ratio between the lengths, always between 0 478 and 1. 479 480 """ 481 OPTIONS = [] 482 name = "depsize" 483

484 - def distance(self, sem1, sem2):

485 from jazzparser.formalisms.music_halfspan.harmstruct import \ 486 semantics_to_dependency_trees 487 # Get dependency graphs for the two logical forms 488 trees1 = semantics_to_dependency_trees(sem1) 489 trees2 = semantics_to_dependency_trees(sem2) 490 # Count the number of dependencies in each graph 491 len1 = sum([len(tree) for tree in trees1]) 492 len2 = sum([len(tree) for tree in trees2]) 493 494 # Take the ratio between the sizes 495 if len1 > len2: 496 return 1.0 - (float(len2) / len1) 497 else: 498 return 1.0 - (float(len1) / len2)

499

Source Code for Module jazzparser.formalisms.music_halfspan.semantics.distance