pycv.cs.ml.cla.boost.adaboost

1 # PyCV - A Computer Vision Package for Python Incorporating Fast Training of Face Detection 2 3 # Copyright 2007 Nanyang Technological University, Singapore. 4 # Authors: Minh-Tri Pham, Viet-Dung D. Hoang, and Tat-Jen Cham. 5 6 # This file is part of PyCV. 7 8 # PyCV is free software: you can redistribute it and/or modify 9 # it under the following term, and the terms of the GNU General Public 10 # License as published by the Free Software Foundation, either version 11 # 3 of the License, or (at your option) any later version. 12 13 # Any published result, involving training a boosted classifier using 14 # at least skewness balancing or polarity balancing, based on running 15 # any method in this file, must cite the following paper: 16 # @INPROCEEDINGS{Pham2007, 17 # author = {Pham, Minh-Tri and Cham, Tat-Jen}, 18 # title = {Online Learning Asymmetric Boosted Classifiers for Object Detection}, 19 # booktitle = {2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007)}, 20 # year = {2007}, 21 # address = {Minneapolis, MN, USA}, 22 # doi = {10.1109/CVPR.2007.383083} 23 # } 24 25 # PyCV is distributed in the hope that it will be useful, 26 # but WITHOUT ANY WARRANTY; without even the implied warranty of 27 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 28 # GNU General Public License for more details. 29 30 # You should have received a copy of the GNU General Public License 31 # along with this program. If not, see <http://www.gnu.org/licenses/>. 32 33 # --------------------------------------------------------------------- 34 #!/usr/bin/env python 35 36 37 __all__ = ['train_DBC', 'train_AdaBoost', 'train_VJ', 'train_PC', \ 38 'convert_scoring2weighted', 'train_OfflineDBC'] 39 40 from copy import copy, deepcopy 41 from math import log, exp, sqrt, fabs 42 from numpy import array, where, zeros, ones, dot, prod 43 from numpy import exp as NP_exp 44 from numpy import log as NP_log 45 from numpy import sqrt as NP_sqrt 46 47 from boosting import DiscreteBoostedClassifier, OnlineDiscreteBoostedClassifier 48 from pycv.cs.ml.cla import CDataset, ScoringCDataset, WeightedCDataset, \ 49 BinaryErrorStats, sort_1d 50 from pycv import tprint, ordinal 51 from pycv.cs.ml import OnlineLearningInterface 52 53

54 -def convert_scoring2weighted(scd):

55 """Convert a binary ScoringCDataset into a WeightedCDataset. 56 57 The formula is weight(x,y) = exp(-y score(x,y)), where y \in {-1,1} 58 59 :Parameters: 60 scd : ScoringCDataset 61 scd must be a binary dataset 62 63 :Returns: 64 wcd : WeightedCDataset 65 """ 66 cd = WeightedCDataset(scd.input_data, \ 67 [NP_exp((1-2*j)*scd.scores[j]) for j in xrange(2)]) 68 cd.normalize_weights() 69 return cd

70 71

72 -def _check_stop_2(scores, maxFAR, maxFRR):

73 cd = CDataset(scores) 74 75 # all examples classified as positive 76 false_pos = cd.nspc[0] 77 false_neg = 0 78 if float(false_pos)/cd.nspc[0] <= maxFAR and float(false_neg)/cd.nspc[1] <= maxFRR: 79 return True 80 81 # sort the scores 82 sorted_cd = sort_1d(cd) 83 84 # move the threshold to check if the the stopping condition has been reached 85 for j, _ in sorted_cd: 86 if j == 0: false_pos -= 1 87 else: false_neg += 1 88 if float(false_pos)/cd.nspc[0] <= maxFAR and float(false_neg)/cd.nspc[1] <= maxFRR: 89 return True 90 # stopping condition has not been reached 91 return False

92 93

94 -def _check_stop_3(scores, maxFAR, maxFRR):

95 cd = CDataset(scores) 96 97 # all examples classified as positive 98 false_pos = cd.nspc[0] 99 false_neg = 0 100 if (float(false_neg)/cd.nspc[1])*maxFAR/maxFRR + (float(false_pos)/cd.nspc[0]) <= maxFAR: 101 return True 102 103 # sort the scores 104 sorted_cd = sort_1d(cd) 105 106 # move the threshold to check if the the stopping condition has been reached 107 for j, _ in sorted_cd: 108 if j == 0: false_pos -= 1 109 else: false_neg += 1 110 if (float(false_neg)/cd.nspc[1])*maxFAR/maxFRR + (float(false_pos)/cd.nspc[0]) <= maxFAR: 111 return True 112 # stopping condition has not been reached 113 return False

114 115

116 -def train_OfflineDBC(scd, trainfunc, M, criterion = 0, param1 = 1.0, \ 117 skewness_balancing=1, preceeding_sc=None, extra_output=False):

118 """Train an offline DiscreteBoostedClassifier 119 120 Criteria: 121 criterion=0: 122 \arg \min_f (\lambda P(1) FRR(f) + P(0) FAR(f)) / \ 123 (\lambda P(1) + P(0)) 124 criterion=1: 125 \arg \min_f (\lambda FRR(f) + FAR(f)) / (\lambda + 1) 126 127 :Paramters: 128 scd : ScoringCDataset 129 a binary ScoringCDataset 130 trainfunc: a function that takes a WeightedCDataset as input 131 and returns a BinaryClassifier as a weak classifier 132 M : int 133 the maximum number of weak classifiers 134 criterion : int 135 which criterion 136 param1 : double 137 \lambda for the criterion 138 skewness_balancing : int 139 type of balancing among weak classifiers 140 0 = no balancing at all, the original AdaBoost's method 141 1 = asymmetric weight balancing, Viola-Jones (NIPS'02) 142 2 = skewness balancing, Pham-Cham (CVPR'07) 143 (N/A if criterion=1) 144 preceeding_sc : ScoringClassifier 145 a classifier to preceed this newly trained one, 146 default is None 147 extra_output : boolean 148 if True then produce extra useful information 149 150 :Returns: 151 dbc : DiscreteBoostedClassifier 152 the newly trained DiscreteBoostedClassifier 153 err : double (extra_output) 154 training error, or training criterion function value 155 scd2 : ScoringCDataset (extra_output) 156 a new ScoringCDataset with scores augmented by this dbc, 157 """ 158 cd = convert_scoring2weighted(scd) 159 160 if criterion==1 and skewness_balancing==2: 161 raise NotImplementedError, 'this case has not been implemented' 162 163 if criterion==1: 164 cd.weights[0] /= cd.weights[0].sum() 165 cd.weights[1] /= cd.weights[1].sum() 166 167 if skewness_balancing == 0: 168 cd.weights[1] *= param1 169 elif skewness_balancing == 1: 170 kk = exp(log(param1)/M) 171 elif skewness_balancing == 2: 172 logk = log(param1) 173 else: 174 raise IndexError('balancing value is out of bound.') 175 176 weaks = [] 177 cs = [] 178 tprint("Training a boosted classifier with at most "+str(M)+" weak classifiers...") 179 for m in xrange(M): 180 if skewness_balancing == 1: 181 cd.weights[1] *= kk 182 elif skewness_balancing == 2: 183 prior = cd.get_twpc() 184 gamma = cd.get_skewness() 185 186 # compute k_m 187 log_k_m = (logk + (M-m-1)*gamma) / (M-m) 188 k_m = exp(log_k_m) 189 190 # update weights to deal with k_m 191 cd.weights[1] *= k_m 192 193 cd.normalize_weights() 194 195 if skewness_balancing == 2: 196 prior = cd.get_twpc() 197 gamma = cd.get_skewness() 198 199 # train the new weak classifier 200 tprint("Training the "+ordinal(m+1)+" weak classifier...") 201 f = trainfunc(cd) 202 203 err = [f.test(cd.input_data[j]) != j for j in xrange(2)] 204 werr = sum([where(err[j],cd.weights[j],0).sum() for j in xrange(2)]) 205 206 if werr < 1e-10: # no single error? too good to be true 207 weaks = [f] 208 cs = [1] 209 break 210 211 c = 0.5 * log((1-werr)/werr) 212 213 # append to the boost 214 weaks.append(f) 215 cs.append(c) 216 217 # update the weights 218 for j in xrange(2): cd.weights[j] *= where(err[j],exp(c),exp(-c)) 219 220 if skewness_balancing == 2: 221 logk -= log_k_m 222 223 dbc = DiscreteBoostedClassifier(preceeding_sc, weaks, array(cs)) 224 if not extra_output: 225 return dbc 226 227 # produce extra information 228 scores = [dbc.scores(x) for x in scd.input_data] 229 scd2 = ScoringCDataset(scd.input_data, scores) 230 err0 = float((scores[0] >= 0).sum()) / scd.nspc[0] # FAR 231 err1 = float((scores[1] < 0).sum()) / scd.nspc[1] # FRR 232 233 if criterion == 0: 234 err = (err0*scd.nspc[0] + err1*scd.nspc[1]*param1) / \ 235 (scd.nspc[0]+scd.nspc[1]*param1) 236 else: #if criterion == 1: 237 err = (err0+err1*param1) / (1+param1) 238 239 return (dbc, err, scd2)

240 241 242 243

244 -def train_DBC(classification_dataset, trainfunc, M, k = 1.0, balancing = 2, \ 245 can_learn=True, polarity_balancing=1, previous=None):

246 """Train a DiscreteBoostedClassifier 247 248 Input: 249 classification_dataset: a WeightedCDataset of 2 classes 250 trainfunc: a function that takes a WeightedCDataset as input 251 and returns a BinaryClassifier as a weak classifier 252 M: the maximum number of weak classifier 253 k: false negatives penalized k times more than false positives 254 balancing: type of balancing among weak classifiers 255 0 = no balancing at all, this is the original AdaBoost's method 256 1 = asymmetric weight balancing, Viola-Jones (NIPS'02) 257 2 = skewness balancing, Pham-Cham (CVPR'07) 258 can_learn : boolean 259 whether the resulting DiscreteBoostedClassifier can learn 260 incrementally 261 polarity_balancing: use polarity balancing for online-learning? 262 0 = no polarity balancing, same as Oza-Rusell (ICSMC'05) 263 1 = polarity balancing, Pham-Cham (CVPR'07) 264 previous: previous additive classifier, default is None 265 Output: 266 a DiscreteBoostedClassifier 267 """ 268 cd = classification_dataset.new() 269 cd.initialize_weights() 270 271 if balancing == 0: 272 cd.weights[1] *= k 273 elif balancing == 1: 274 kk = exp(log(k)/M) 275 elif balancing == 2: 276 logk = log(k) 277 else: 278 raise IndexError('balancing value is out of bound.') 279 280 weaks = [] 281 cs = [] 282 tprint("Training a boosted classifier with at most "+str(M)+" weak classifiers...") 283 for m in xrange(M): 284 if balancing == 1: 285 cd.weights[1] *= kk 286 elif balancing == 2: 287 prior = cd.get_twpc() 288 gamma = cd.get_skewness() 289 290 # tprint("Before applying k_m:") 291 # tprint("m="+str(m)) 292 # tprint("log k="+str(logk)) 293 # tprint("prior="+str(prior)) 294 # tprint("gamma="+str(gamma)) 295 296 # compute k_m 297 log_k_m = (logk + (M-m-1)*gamma) / (M-m) 298 k_m = exp(log_k_m) 299 # tprint("log k_m="+str(log_k_m)) 300 # tprint("k_m="+str(k_m)) 301 302 # update weights to deal with k_m 303 cd.weights[1] *= k_m 304 305 cd.normalize_weights() 306 307 if balancing == 2: 308 # tprint("After applying k_m:") 309 prior = cd.get_twpc() 310 gamma = cd.get_skewness() 311 # tprint("prior="+str(prior)) 312 # tprint("gamma="+str(gamma)) 313 314 # train the new weak classifier 315 tprint("Training the "+ordinal(m+1)+" weak classifier...") 316 f = trainfunc(cd) 317 318 err = [f.test(cd.input_data[j]) != j for j in xrange(2)] 319 werr = sum([where(err[j],cd.weights[j],0).sum() for j in xrange(2)]) 320 321 if werr < 1e-20: # no single error? too good to be true 322 weaks = [f] 323 cs = [1] 324 break 325 326 c = 0.5 * log((1-werr)/werr) 327 328 # append to the boost 329 weaks.append(f) 330 cs.append(c) 331 332 # update the weights 333 for j in xrange(2): cd.weights[j] *= where(err[j],exp(c),exp(-c)) 334 335 if balancing == 2: 336 logk -= log_k_m 337 338 if can_learn: 339 return OnlineDiscreteBoostedClassifier(previous, weaks, array(cs), k, 340 balancing, polarity_balancing) 341 else: 342 return DiscreteBoostedClassifier(previous, weaks, array(cs))

343

344 -def train_AdaBoost(classification_dataset, trainfunc, M, 345 can_learn=True, polarity_balancing=1):

346 """Train a DiscreteBoostedClassifier using AdaBoost (Friend et al's DiscreteAdaboost) 347 348 Warning: 349 This function is now obsolete, use train_DBC() instead. 350 351 Input: 352 classification_dataset: a WeightedCDataset of 2 classes 353 trainfunc: a function that takes a WeightedCDataset as input 354 and returns a BinaryClassifier 355 M: the maximum number of stages 356 can_learn : boolean 357 whether the resulting DiscreteBoostedClassifier can learn 358 incrementally 359 polarity_balancing: use polarity balancing for online-learning? 360 0 = no polarity balancing, same as Oza-Rusell (ICSMC'05) 361 1 = polarity balancing, Pham-Cham (CVPR'07) 362 Output: 363 a DiscreteBoostedClassifier 364 """ 365 cd = classification_dataset.new() 366 cd.initialize_weights() 367 368 weaks = [] 369 cs = [] 370 for m in xrange(M): 371 # train the new weak classifier 372 tprint("Training the "+ordinal(m+1)+" weak classifier.") 373 f = trainfunc(cd) 374 375 err = [f.test(cd.input_data[j]) != j for j in xrange(2)] 376 werr = sum([where(err[j],cd.weights[j],0).sum() for j in xrange(2)]) 377 378 if werr < 1e-20: # no single error? too good to be true 379 weaks = [f] 380 cs = [1] 381 break 382 383 c = 0.5 * log((1-werr)/werr) 384 385 # append to the boost 386 weaks.append(f) 387 cs.append(c) 388 389 # update the weights, then normalize 390 for j in xrange(2): cd.weights[j] *= where(err[j],exp(c),exp(-c)) 391 cd.normalize_weights() 392 393 if can_learn: 394 return OnlineDiscreteBoostedClassifier(None, weaks, array(cs), 1.0, 395 0, polarity_balancing) 396 else: 397 return DiscreteBoostedClassifier(None, weaks, array(cs))

398 399

400 -def train_VJ( classification_dataset, trainfunc, M, k, evenly = True, 401 can_learn=True, polarity_balancing=1 ):

402 """Train a DiscreteBoostedClassifier using Viola and Jones' 403 asymmetric boost (NIPS'02) 404 405 Warning: 406 This function is now obsolete, use train_DBC() instead. 407 408 Input: 409 classification_dataset: a WeightedCDataset of 2 classes 410 trainfunc: a function that takes a WeightedCDataset as input 411 and returns a BinaryClassifier 412 M: the maximum number of stages 413 k: false negatives penalized k times more than false positives 414 evenly: distribute lambda evenly among the weak classifiers 415 can_learn : boolean 416 whether the resulting DiscreteBoostedClassifier can learn 417 incrementally 418 polarity_balancing: use polarity balancing for online-learning? 419 0 = no polarity balancing, same as Oza-Rusell (ICSMC'05) 420 1 = polarity balancing, Pham-Cham (CVPR'07) 421 Output: 422 a DiscreteBoostedClassifier 423 """ 424 cd = classification_dataset.new() 425 cd.initialize_weights() 426 427 if evenly == True: 428 kk = exp(log(k)/M) 429 else: 430 cd.weights[1] *= k 431 432 weaks = [] 433 cs = [] 434 tprint("Training a boosted classifier with at most "+str(M)+" weak classifiers...") 435 for m in xrange(M): 436 if evenly == True: cd.weights[1] *= kk 437 cd.normalize_weights() 438 439 # train the new weak classifier 440 tprint("Training the "+ordinal(m+1)+" weak classifier...") 441 f = trainfunc(cd) 442 443 err = [f.test(cd.input_data[j]) != j for j in xrange(2)] 444 werr = sum([where(err[j],cd.weights[j],0).sum() for j in xrange(2)]) 445 446 if werr < 1e-20: # no single error? too good to be true 447 weaks = [f] 448 cs = [1] 449 break 450 451 c = 0.5 * log((1-werr)/werr) 452 453 # append to the boost 454 weaks.append(f) 455 cs.append(c) 456 457 # update the weights 458 for j in xrange(2): cd.weights[j] *= where(err[j],exp(c),exp(-c)) 459 460 if can_learn: 461 return OnlineDiscreteBoostedClassifier(None, weaks, array(cs), k, 462 1, polarity_balancing) 463 else: 464 return DiscreteBoostedClassifier(None, weaks, array(cs))

465 466

467 -def train_PC( classification_dataset, trainfunc, M, k, 468 can_learn=True, polarity_balancing=1 ):

469 """Train a DiscreteBoostedClassifier using our (Pham and Cham's) 470 asymmetric boost (CVPR'07) 471 472 Warning: 473 This function is now obsolete, use train_DBC() instead. 474 475 Input: 476 classification_dataset: a WeightedCDataset of 2 classes 477 trainfunc: a function that takes a WeightedCDataset as input 478 and returns a BinaryClassifier 479 M: the maximum number of stages 480 k: false negatives penalized k times more than false positives 481 can_learn : boolean 482 whether the resulting DiscreteBoostedClassifier can learn 483 incrementally 484 polarity_balancing: use polarity balancing for online-learning? 485 0 = no polarity balancing, same as Oza-Rusell (ICSMC'05) 486 1 = polarity balancing, Pham-Cham (CVPR'07) 487 Output: 488 a DiscreteBoostedClassifier 489 """ 490 cd = classification_dataset.new() 491 cd.initialize_weights() 492 493 logk = log(k) 494 495 weaks = [] 496 cs = [] 497 for m in xrange(M): 498 # train the new weak classifier 499 tprint("Training the "+ordinal(m+1)+" weak classifier.") 500 501 prior = cd.get_twpc() 502 gamma = cd.get_skewness() 503 504 # tprint("Before applying k_m:") 505 # tprint("m="+str(m)) 506 # tprint("log k="+str(logk)) 507 # tprint("prior="+str(prior)) 508 # tprint("gamma="+str(gamma)) 509 510 # compute k_m 511 log_k_m = (logk + (M-m-1)*gamma) / (M-m) 512 k_m = exp(log_k_m) 513 # tprint("log k_m="+str(log_k_m)) 514 # tprint("k_m="+str(k_m)) 515 516 # update weights to deal with k_m 517 cd.weights[1] *= k_m 518 519 # tprint("After applying k_m:") 520 cd.normalize_weights() 521 prior = cd.get_twpc() 522 gamma = cd.get_skewness() 523 # tprint("prior="+str(prior)) 524 # tprint("gamma="+str(gamma)) 525 526 f = trainfunc(cd) 527 528 err = [f.test(cd.input_data[j]) != j for j in xrange(2)] 529 werr = sum([where(err[j],cd.weights[j],0).sum() for j in xrange(2)]) 530 531 if werr < 1e-20: # no single error? too good to be true 532 weaks = [f] 533 cs = [1] 534 break 535 536 c = 0.5 * log((1-werr)/werr) 537 538 # append to the boost 539 weaks.append(f) 540 cs.append(c) 541 542 # update the weights, then normalize 543 for j in xrange(2): cd.weights[j] *= where(err[j],exp(c),exp(-c)) 544 cd.normalize_weights() 545 logk -= log_k_m 546 547 if can_learn: 548 return OnlineDiscreteBoostedClassifier(None, weaks, array(cs), k, 549 2, polarity_balancing) 550 else: 551 return DiscreteBoostedClassifier(None, weaks, array(cs))

552 553 554

555 -def train_PC_NIPS( classification_dataset, trainfunc, M, k ):

556 """Train a DiscreteBoostedClassifier using our (Pham and Cham's) 557 asymmetric boost (NIPS'07 -- never submitted) 558 559 Goal: 560 Assume D^+ is the distribution of x given x positive. 561 Assume D^- is the distribution of x given x negative. 562 We wish to find F_M(x) to minimize: 563 k J^-(F_M) + J^+(F_M) (1) 564 where 565 J^+(F_M) = E_{D^+} [(F_M(x)-1)^2] 566 J^-(F_M) = E_{D^-} [(F_M(x)+1)^2] 567 568 Let: 569 pi^+_m = 1 - E_{D^+} [F_M(x)] 570 pi^-_m = 1 - E_{D^-} [F_M(x)] 571 D^+_m a distribution such that p_{D^+_m}(x) = p_{D^+}(x) (1-F_m(x)) / pi^+_m 572 D^-_m a distribution such that p_{D^-_m}(x) = p_{D^-}(x) (1+F_m(x)) / pi^-_m 573 FRR_m(f) = E_{D^+_m}[f(x) == -1] 574 FAR_m(f) = E_{D^-_m}[f(x) == +1] 575 576 I proved that: 577 J^+(F_M) = J^+(F_m) + c^2 + 2 c pi^+_m (2FRR_m(f) - 1) 578 J^-(F_M) = J^-(F_m) + c^2 + 2 c pi^-_m (2FAR_m(f) - 1) 579 580 Let's say we want to minimize (1) then we need to 581 1) choose f minimizing: (weak classifier) 582 epsilon(f) = k pi^-_m FRR_m(f) + k pi^+_m FAR_m(f) 583 2) choose minimizing: (voting coefficient) 584 (k J^- + J^+)(F_m) + (k+1) c^2 + 4c epsilon(f) - 2c(k pi^-_m + pi^+_m) 585 which means: 586 c* = \frac{k pi^-_m + pi^+_m - 2 epsilon(f)} {k+1} 587 588 I also proved that: (not quite) 589 |F_M(x)| <= \sum_{m=1}^M |c_m| <= 1 for all M 590 591 592 Input: 593 classification_dataset: a WeightedCDataset of 2 classes 594 trainfunc: a function that takes a WeightedCDataset as input 595 and returns a BinaryClassifier 596 M: the maximum number of stages 597 k: false negative rate penalized k times more than false positive rate 598 Output: 599 a DiscreteBoostedClassifier 600 """ 601 raise NotImplementedError, "the function has not been implemented"

602 603 604 605 # class RealAdaboostClassifier(BinaryClassifier): # binary classifier 606 607 # def __init__(self,maxM,weak_probabilistic_binary_classifier): 608 # classifier.__init__(self,2) 609 # self.maxM = maxM 610 # self.apclassifier = weak_probabilistic_binary_classifier 611 612 # def train( self, input_data, weights = None, *args ): 613 # BinaryClassifier.train( self, input_data, weights, *args ) 614 # N = map(len,input_data) 615 # if weights is None: 616 # w = [ones(n)/sum(N) for n in N] 617 # else: 618 # w = weights.copy() 619 620 # self.weaks = [] 621 # self.c = [] 622 # for m in xrange(maxM): 623 #train the new weak classifier 624 # weak = copy(self.apclassifier) 625 # weak.train(input_data,w,*args) 626 627 #append to the boost 628 # self.weaks.append(weak) 629 630 #update the weights 631 # for j in xrange(2): 632 # z = weak.test_pdf(input_data[j]) 633 # w[j] *= NP_sqrt(z[1-j]/z[j]) 634 635 # def predict(self,input_point): 636 # val = 0 637 # for w in self.weaks: 638 # pdf = w.predict_pdf(input_point) 639 # val += 0.5 * log(pdf[1]/pdf[0]) 640 # return int(val >= 0) 641 642 643 # def main(): 644 #main idea is for testing 645 # a = [array([[0,1],[1,1],[1,0]]),array([[0,2],[1,2],[2,2],[2,1],[2,0]])] 646 # b = WeightedCDataset(a) 647 # c = train_PC(b,train_NBClassifier,10,10000) 648 # tprint(c.test(a[0])) 649 # tprint(c.test(a[1])) 650 651 # if __name__ == '__main__': 652 # main() 653

Source Code for Module pycv.cs.ml.cla.boost.adaboost