teamwork.math.rules

1 """Code for manipulating a rule-based representation of PWL functions""" 2 import copy 3 4 __PROFILE__ = False 5 if __PROFILE__: 6 import hotshot,hotshot.stats 7

8 -class Rule(dict):

9 """Representation of a single rule. The left-hand side of the rule is a dictionary of attribute-value pairs. The rule fires on inputs that whose value on each attribute matches that of the rule. A rule with a value of C{None} for a given attribute is indifferent to the input value for the attribute. 10 @ivar rhs: the value of the rule if it fires 11 """

12 - def __init__(self,lhs={},rhs=None):

13 """ 14 @param lhs: the initial attribute-value pairs for the left-hand side of this rule 15 @type lhs: dict 16 @param rhs: the right-hand side of the rule 17 """ 18 dict.__init__(self,lhs) 19 self.rhs = rhs

20

21 - def test(self,state,attributes):

22 """Determines whether this rule fires under the given conditions 23 @param attributes: the mapping from attribute labels to actual hyperplane conditions 24 @type attributes: dict:strS{->}L{teamwork.math.matrices.Hyperplane} 25 @param state: the current point to test this rule's LHS against 26 @type state: L{teamwork.math.probability.Distribution} 27 @return: C{True} iff this rule matches the given state 28 @rtype: bool 29 """ 30 if len(state.domain()) > 1: 31 raise NotImplementedError,'Rules currently unable to handle uncertainty' 32 else: 33 state = state.domain()[0] 34 for attr,truth in self.items(): 35 if truth is not None: 36 plane = attributes[attr] 37 if plane.test(state) != truth: 38 break 39 else: 40 return True 41 return False

42

43 - def __copy__(self):

44 return self.__class__(self,self.rhs)

45

46 -def applyRules(state,rules,attributes,values,target,checkForDuplicates=False):

47 if len(state.domain()) > 1: 48 raise NotImplementedError,'Rules currently unable to handle uncertainty' 49 else: 50 state = state.domain()[0] 51 rhs = [] 52 for rule in rules: 53 for attr,truth in rule.items(): 54 if attr != target and truth is not None: 55 plane = attributes[attr] 56 if plane.test(state) != truth: 57 break 58 else: 59 if checkForDuplicates: 60 # Accumulate all matches 61 rhs.append(values[rule[target]]) 62 else: 63 # Just exit with the first match we find 64 return values[rule[target]] 65 if checkForDuplicates: 66 assert(len(rules) == 0 or len(rhs) > 0) 67 for rule in rhs[1:]: 68 assert(rule == rhs[0]) 69 return rhs[0]

70

71 -def mergeAttributes(original,rules,new):

72 for myAttr,myPlane in new.items(): 73 if original.has_key(myAttr): 74 # Already have this attribute, so nothing to do 75 pass 76 elif myAttr == '_value': 77 pass 78 else: 79 for yrAttr,yrPlane in original.items(): 80 if yrAttr == '_value': 81 pass 82 elif yrPlane.compare(myPlane) == 'equal': 83 # Identical attribute, but with a different label 84 for rule in rules: 85 try: 86 rule[yrAttr] = rule[myAttr] 87 del rule[myAttr] 88 except KeyError: 89 # We may have more than one attribute in original that are equal to myAttr? 90 pass 91 break 92 else: 93 # New attribute 94 original[myAttr] = myPlane

95

96 -def internalCheck(rules,attributes,values,target,debug=False):

97 """Test whether any redundant/inconsistent attribute assignments are present 98 """ 99 lhs = filter(lambda k:k != target,attributes.keys()) 100 comparisons = {} 101 newAttributes = {target:True} 102 newRules = [] 103 for rule in rules: 104 if debug: 105 print 106 for attr,value in rule.items(): 107 if attr != target: # and value is not None: 108 print value,attr 109 rule = copy.copy(rule) 110 newRules.append(rule) 111 for myIndex in range(len(lhs)): 112 myAttr = lhs[myIndex] 113 myPlane = attributes[myAttr] 114 for yrIndex in range(myIndex+1,len(lhs)): 115 yrAttr = lhs[yrIndex] 116 ## assert(myAttr != yrAttr) 117 yrPlane = attributes[yrAttr] 118 try: 119 result = comparisons[yrAttr][myAttr] 120 except KeyError: 121 result = yrPlane.compare(myPlane) 122 try: 123 comparisons[yrAttr][myAttr] = result 124 except KeyError: 125 comparisons[yrAttr] = {myAttr:result} 126 if result == 'equal': 127 if isinstance(rule[myAttr],bool) and isinstance(rule[yrAttr],bool): 128 if debug: 129 print 'Attribute:',myAttr,rule[myAttr] 130 print 'Redundant given:',yrAttr,rule[yrAttr] 131 if rule[myAttr] != rule[yrAttr]: 132 # Inconsistent (unlikely to ever happen) 133 if debug: 134 print '\tRule inconsistency' 135 newRules.pop() 136 break 137 elif result == 'greater' and rule.has_key(yrAttr) and rule[yrAttr] == True: 138 if debug: 139 print 'Attribute:',myAttr,rule[myAttr] 140 print 'Eliminated by greater:',yrAttr,rule[yrAttr] 141 if rule.has_key(myAttr) and rule[myAttr] == False: 142 # Inconsistent 143 if debug: 144 print '\tRule inconsistency' 145 newRules.pop() 146 break 147 else: 148 # Redundant 149 rule[myAttr] = None 150 break 151 elif result == 'less' and rule.has_key(yrAttr) and rule[yrAttr] == False: 152 if debug: 153 print 'Attribute:',myAttr,rule[myAttr] 154 print 'Eliminated by lesser:',yrAttr,rule[yrAttr] 155 if rule.has_key(myAttr) and rule[myAttr] == True: 156 # Inconsistent 157 if debug: 158 print '\tRule inconsistency' 159 newRules.pop() 160 break 161 else: 162 # Redundant 163 rule[myAttr] = None 164 break 165 else: 166 ## for yrAttr,yrPlane in newAttributes.items(): 167 ## assert(isinstance(yrPlane,bool) or yrPlane.compare(myPlane) != 'equal' \ 168 ## or (myAttr == yrAttr)) 169 newAttributes[myAttr] = attributes[myAttr] 170 if len(newRules) == 0 or rule is not newRules[-1]: 171 break 172 if debug: 173 print 174 for attr in newAttributes.keys(): 175 value = rule[attr] 176 if attr != target and value is not None: 177 print value,attr 178 from Keys import StateKey 179 try: 180 print values[rule[target]][StateKey({'entity':'GeographicArea','feature':'oilInfrastructure'})] 181 except KeyError: 182 pass 183 print '-------------------------------------------------------------------' 184 for rule in newRules: 185 for attr in rule.keys(): 186 if not newAttributes.has_key(attr): 187 del rule[attr] 188 if debug: 189 print 'Internal inconsistencies eliminated:', 190 print len(rules)-len(newRules),'rules', 191 print len(attributes)-len(newAttributes),'attributes' 192 return newRules,newAttributes

193

194 -def clusterRules(rules,values):

195 print len(rules) 196 newRules = [] 197 lhsKeys = filter(lambda k:k!='_value',rules[0].keys()) 198 for value in values.keys(): 199 onesToRules = map(lambda i: [],range(pow(2,len(lhsKeys)))) 200 rulesToOnes = [] 201 for ruleIndex in range(len(rules)): 202 rule = rules[ruleIndex] 203 if rule['_value'] == value: 204 ones = [0] 205 for attrIndex in range(len(lhsKeys)): 206 attr = lhsKeys[attrIndex] 207 if rule[attr] == True: 208 ones = map(lambda v:v+pow(2,attrIndex),ones) 209 elif rule[attr] is None: 210 ones = sum(map(lambda v:[v,v+pow(2,attrIndex)],ones),[]) 211 for one in ones: 212 onesToRules[one].append(ruleIndex) 213 else: 214 ones = [] 215 rulesToOnes.append(ones) 216 missing = True 217 essential = {} 218 for one in onesToRules: 219 if len(one) == 1: 220 essential[one[0]] = True 221 while missing: 222 missing = False 223 for one in onesToRules: 224 if len(one) > 0: 225 for rule in one: 226 if essential.has_key(rule): 227 # Already covered 228 break 229 else: 230 missing = True 231 essential[one[0]] = True 232 for rule in essential.keys(): 233 newRules.append(rules[rule]) 234 print len(newRules)

235

236 -def pruneRules(original,attributes,values,debug=False):

237 if debug: 238 print 'Starting with:',len(original) 239 target = '_value' 240 rules,newAttributes = internalCheck(original,attributes,values,target,debug=False) 241 lhs = filter(lambda k:k != target,newAttributes.keys()) 242 # Cluster rules based on RHS values 243 values = {} 244 for rule in rules: 245 try: 246 values[rule[target]].append(rule) 247 except KeyError: 248 values[rule[target]] = [rule] 249 for value,ruleSet in values.items(): 250 change = True 251 while change: 252 change = False 253 newRules = [] 254 for myIndex in range(len(ruleSet)): 255 # Loop through each rule 256 myRule = ruleSet[myIndex] 257 merged = [] 258 for yrIndex in range(myIndex+1,len(ruleSet)): 259 # Loop through any candidates for merging 260 yrRule = ruleSet[yrIndex] 261 difference = None 262 for attr in lhs: 263 try: 264 myValue = myRule[attr] 265 except KeyError: 266 myValue = None 267 try: 268 yrValue = yrRule[attr] 269 except KeyError: 270 yrValue = None 271 if isinstance(myValue,bool) and \ 272 isinstance(yrValue,bool): 273 if myValue != yrValue: 274 # These rules have opposite conditions 275 if difference is None: 276 # First difference found 277 difference = attr 278 else: 279 # More than one difference is useless 280 break 281 elif myValue != yrValue: 282 # None is treated as not matching T/F 283 break 284 else: 285 ## if debug: 286 ## print 'Merging:' 287 ## print map(lambda k:myRule[k],lhs) 288 ## print map(lambda k:yrRule[k],lhs) 289 rule = copy.copy(myRule) 290 if difference is None: 291 # These two rules are identical 292 if myRule[target] != yrRule[target]: 293 raise UserWarning,'Mismatched identitical rules found' 294 else: 295 # These two rules differ in only one condition 296 rule[difference] = None 297 merged.append(rule) 298 if len(merged) > 0: 299 # We merged this rule with others 300 newRules += merged 301 change = True 302 else: 303 newRules.append(myRule) 304 if change: 305 # Find any redundant rules 306 myIndex = 0 307 while myIndex < len(newRules): 308 myRule = newRules[myIndex] 309 yrIndex = myIndex + 1 310 while yrIndex < len(newRules): 311 yrRule = newRules[yrIndex] 312 subsumes = True 313 isSubsumed = True 314 for attr in newAttributes.keys(): 315 if attr != target: 316 try: 317 myValue = myRule[attr] 318 except KeyError: 319 myValue = None 320 try: 321 yrValue = yrRule[attr] 322 except KeyError: 323 yrValue = None 324 if isinstance(myValue,bool): 325 if isinstance(yrValue,bool): 326 if myValue != yrValue: 327 # Mismatch 328 subsumes = False 329 isSubsumed = False 330 break 331 else: 332 # yrRule is more general 333 subsumes = False 334 elif isinstance(yrValue,bool): 335 # yrRule is more specific 336 isSubsumed = False 337 else: 338 # Both are indifferent 339 pass 340 else: 341 if subsumes: 342 # yrRule is redundant 343 ## if debug: 344 ## print 'Redundancy:' 345 ## print map(lambda k:myRule[k],lhs),'subsumes' 346 ## print map(lambda k:yrRule[k],lhs) 347 if myRule[target] != yrRule[target]: 348 raise UserWarning,'Identical conditions lead to different RHS values!' 349 else: 350 del newRules[yrIndex] 351 # Go on to next rule 352 continue 353 elif isSubsumed: 354 # myRule is redundant 355 ## if debug: 356 ## print 'Redundancy:' 357 ## print map(lambda k:yrRule[k],lhs),'subsumes' 358 ## print map(lambda k:myRule[k],lhs) 359 del newRules[myIndex] 360 break 361 yrIndex += 1 362 else: 363 myIndex += 1 364 if debug: 365 if len(ruleSet) != len(newRules): 366 print 'Reducing rule set by:',len(ruleSet)-len(newRules) 367 ruleSet = newRules 368 if len(ruleSet) == 1: 369 # No need to continue if we're already down to one rule 370 change = False 371 values[value] = ruleSet 372 # Check whether any conditions have been made irrelevant 373 ruleSet = sum(values.values(),[]) 374 unused = {} 375 for attr in ruleSet[0].keys(): 376 if attr != target and ruleSet[0][attr] is None: 377 # This attribute is unused by the first rule 378 unused[attr] = True 379 for rule in ruleSet[1:]: 380 for attr in unused.keys(): 381 if rule.has_key(attr) and rule[attr] is not None: 382 # This attribute is used by this rule 383 del unused[attr] 384 # Delete any unused attributes 385 for attr in unused.keys(): 386 del newAttributes[attr] 387 for rule in ruleSet: 388 if rule.has_key(attr): 389 del rule[attr] 390 if debug: 391 print 'Overall reduction:',len(rules)-len(ruleSet) 392 return ruleSet,newAttributes

393

394 -def addRules(set1,set2,attributes,values):

395 result = [] 396 target = '_value' 397 lhsKeys = filter(lambda k:k!=target,attributes.keys()) 398 for new in set2: 399 newValue = values[new[target]] 400 for old in set1: 401 rule = {} 402 for attr in lhsKeys: 403 if not old.has_key(attr): 404 old[attr] = None 405 if not new.has_key(attr): 406 new[attr] = None 407 if old[attr] is None: 408 # Old rule is indifferent, so use new rule 409 rule[attr] = new[attr] 410 elif new[attr] is None: 411 # Old rule has restriction, but new rule is indifferent 412 rule[attr] = old[attr] 413 elif old[attr] == new[attr]: 414 # Both rules have the same restriction 415 rule[attr] = old[attr] 416 else: 417 # Mismatch 418 break 419 else: 420 oldValue = values[old[target]] 421 newValue = values[new[target]] 422 total = oldValue + newValue 423 label = str(total) 424 rule[target] = label 425 if not values.has_key(label): 426 values[label] = total 427 result.append(rule) 428 for rule in result: 429 for attr in lhsKeys: 430 if not rule.has_key(attr): 431 rule[attr] = None 432 return result

433

434 -def multiplyRules(set1,set2,attributes,values,interrupt=None):

435 if __PROFILE__: 436 filename = '/tmp/stats' 437 prof = hotshot.Profile(filename) 438 prof.start() 439 comparisons = {} 440 cache = {} 441 newRules = [] 442 target = '_value' 443 lhsKeys = filter(lambda k:k!=target,attributes.keys()) 444 newAttributes = {} 445 newPlanes = {} 446 for new in set1: 447 for old in set2: 448 # Examine every pairwise combination of rules 449 matrix = values[old[target]] 450 inconsistent = False 451 projectedNew = {} 452 for newAttr,newValue in new.items(): 453 if newAttr != target and newValue is not None: 454 # Transform each hyperplane in the new rule by the RHS of the old 455 try: 456 label = cache[newAttr][old[target]] 457 newPlane = newPlanes[label] 458 except KeyError: 459 newPlane = attributes[newAttr] 460 weights = newPlane.weights * matrix 461 newPlane = newPlane.__class__(weights, 462 newPlane.threshold) 463 label = newPlane.simpleText() 464 newPlanes[label] = newPlane 465 try: 466 cache[newAttr][old[target]] = label 467 except KeyError: 468 cache[newAttr] = {old[target]:label} 469 # Identify any conflicts/redundancies with the conditions of old rule 470 for oldAttr,oldValue in old.items(): 471 if interrupt and interrupt.isSet(): 472 return None 473 if oldAttr != target and oldValue is not None: 474 oldPlane = attributes[oldAttr] 475 try: 476 result = comparisons[oldAttr][label] 477 except KeyError: 478 result = oldPlane.compare(newPlane) 479 try: 480 comparisons[oldAttr][label] = result 481 except KeyError: 482 comparisons[oldAttr] = {label:result} 483 if result == 'equal': 484 label = oldAttr 485 for attr,plane in newAttributes.items(): 486 if attr != target and attr != label: 487 try: 488 result = comparisons[label][attr] 489 except KeyError: 490 result = newPlane.compare(plane) 491 try: 492 comparisons[label][attr] = result 493 except KeyError: 494 comparisons[label] = {attr:result} 495 if result == 'equal': 496 label = attr 497 break 498 else: 499 newAttributes[label] = attributes[label] 500 if projectedNew.has_key(label): 501 if projectedNew[label] is None: 502 projectedNew[label] = newValue 503 elif newValue is not None and \ 504 projectedNew[label] != newValue: 505 inconsistent = True 506 else: 507 projectedNew[label] = newValue 508 if projectedNew[label] is None: 509 # Old rule takes precedence 510 projectedNew[label] = oldValue 511 elif projectedNew[label] != oldValue: 512 # Mismatch 513 inconsistent = True 514 break 515 elif result == 'greater' and oldValue == True: 516 # newAttr is guaranteed to be True 517 if newValue == False: 518 inconsistent = True 519 break 520 elif result == 'less' and oldValue == False: 521 # newAttr is guaranteed to be False 522 if newValue == True: 523 inconsistent = True 524 break 525 else: 526 for attr,plane in newAttributes.items(): 527 if attr != target and attr != label: 528 try: 529 result = comparisons[label][attr] 530 except KeyError: 531 result = newPlane.compare(plane) 532 try: 533 comparisons[label][attr] = result 534 except KeyError: 535 comparisons[label] = {attr:result} 536 if result == 'equal': 537 label = attr 538 break 539 if newAttributes.has_key(label): 540 projectedNew[label] = newValue 541 elif attributes.has_key(label): 542 if old.has_key(label) and old[label] is not None and old[label] != newValue: 543 # Mismatch 544 inconsistent = True 545 break 546 projectedNew[label] = newValue 547 newAttributes[label] = attributes[label] 548 cache[newAttr][old[target]] = label 549 else: 550 # No matching plane found 551 newAttributes[label] = newPlane 552 cache[newAttr][old[target]] = label 553 lhsKeys.append(label) 554 projectedNew[label] = newValue 555 if inconsistent: 556 # Once we've found an inconsistency, no need to examine rest of this rule 557 break 558 if inconsistent: 559 # These two rules are incompatible 560 continue 561 for oldAttr,oldValue in old.items(): 562 if oldAttr == target or oldValue is None: 563 pass 564 else: 565 oldPlane = attributes[oldAttr] 566 for newAttr,newPlane in newAttributes.items(): 567 if oldPlane.compare(newPlane) == 'equal': 568 break 569 else: 570 newAttributes[oldAttr] = attributes[oldAttr] 571 newAttr = oldAttr 572 if projectedNew.has_key(newAttr): 573 pass 574 else: 575 projectedNew[newAttr] = oldValue 576 # Compute new RHS 577 try: 578 label = cache[old[target]][new[target]] 579 except KeyError: 580 oldValue = values[old[target]] 581 newValue = values[new[target]] 582 product = newValue * oldValue 583 label = product.simpleText() 584 if not values.has_key(label): 585 values[label] = product 586 try: 587 cache[old[target]][new[target]] = label 588 except KeyError: 589 cache[old[target]] = {new[target]:label} 590 projectedNew[target] = label 591 newRules.append(projectedNew) 592 newAttributes[target] = True 593 if __PROFILE__: 594 prof.stop() 595 prof.close() 596 print 'loading stats...',len(set1), len(set2) 597 stats = hotshot.stats.load(filename) 598 stats.strip_dirs() 599 stats.sort_stats('time', 'calls') 600 stats.print_stats() 601 raise UserWarning 602 return newRules,newAttributes

603

604 -def mapValues(rules,values,op):

605 """Applies a fixed transformation to the RHS of a set of rules 606 @param rules: the set of rules to transform (left unchanged) 607 @type rules: dict[] 608 @param values: the dictionary of current RHS values 609 @type values: dict 610 @param op: the transformation, a function that takes a single RHS value as input and returns the new RHS value (assumed to be a 1-1 mapping) 611 """ 612 target = '_value' 613 cache = {} 614 used = {} 615 result = [] 616 for rule in rules: 617 rule = copy.copy(rule) 618 try: 619 label = cache[rule[target]] 620 except KeyError: 621 newRHS = op(values[rule[target]]) 622 label = str(newRHS) 623 cache[rule[target]] = label 624 if not values.has_key(label): 625 values[label] = newRHS 626 used[label] = True 627 rule[target] = label 628 result.append(rule) 629 for label in values.keys(): 630 if not used.has_key(label): 631 del values[label] 632 return result

633

634 -def replaceValues(rules,attributes,oldValues,mapping,newValues):

635 """Use RHS values to trigger a second set of rules, and return a merged set of the two 636 @param rules: the original rule set 637 @type rules: dict[] 638 @param attributes: the attribute set for both sets of rules 639 @type attributes: dict 640 @param oldValues: the set of values for only the original set of rules 641 @type oldValues: dict 642 @param mapping: a dictionary of rule sets, indexed by value labels from the original set of rules 643 @type mapping: dict:strS{->}dict[] 644 @param newValues: the set of values for only the new set of rules 645 @type newValues: dict 646 @return: the new rules merging the two sets 647 @rtype: dict[] 648 """ 649 result = [] 650 target = '_value' 651 lhsKeys = filter(lambda k:k!=target,attributes.keys()) 652 for old in rules: 653 for new in mapping[old[target]]: 654 rule = {} 655 for attr in lhsKeys: 656 if not old.has_key(attr) or old[attr] is None: 657 # Old rule is indifferent, so use new rule 658 try: 659 rule[attr] = new[attr] 660 except KeyError: 661 # New rule is indifferent, too 662 rule[attr] = None 663 elif not new.has_key(attr) or new[attr] is None: 664 # Old rule has restriction, but new rule is indifferent 665 rule[attr] = old[attr] 666 elif old[attr] == new[attr]: 667 # Both rules have the same restriction 668 rule[attr] = old[attr] 669 else: 670 # Mismatch 671 break 672 else: 673 rule[target] = new[target] 674 result.append(rule) 675 return result

676

Source Code for Module teamwork.math.rules