Robust/src/Benchmarks/SingleTM/Bayes/Learner.java

   1 /* =============================================================================
   2  *
   3  * learner.java
   4  * -- Learns structure of Bayesian net from data
   5  *
   6  * =============================================================================
   7  *
   8  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   9  * Author: Chi Cao Minh
  10  * Ported to Java June 2009 Alokika Dash
  11  * University of California, Irvine
  12  *
  13  *
  14  * =============================================================================
  15  *
  16  * The penalized log-likelihood score (Friedman & Yahkani, 1996) is used to
  17  * evaluated the "goodness" of a Bayesian net:
  18  *
  19  *                             M      n_j
  20  *                            --- --- ---
  21  *  -N_params * ln(R) / 2 + R >   >   >   P((a_j = v), X_j) ln P(a_j = v | X_j)
  22  *                            --- --- ---
  23  *                            j=1 X_j v=1
  24  *
  25  * Where:
  26  *
  27  *     N_params     total number of parents across all variables
  28  *     R            number of records
  29  *     M            number of variables
  30  *     X_j          parents of the jth variable
  31  *     n_j          number of attributes of the jth variable
  32  *     a_j          attribute
  33  *
  34  * The second summation of X_j varies across all possible assignments to the
  35  * values of the parents X_j.
  36  *
  37  * In the code:
  38  *
  39  *    "local log likelihood" is  P((a_j = v), X_j) ln P(a_j = v | X_j)
  40  *    "log likelihood" is everything to the right of the '+', i.e., "R ... X_j)"
  41  *    "base penalty" is -ln(R) / 2
  42  *    "penalty" is N_params * -ln(R) / 2
  43  *    "score" is the entire expression
  44  *
  45  * For more notes, refer to:
  46  *
  47  * A. Moore and M.-S. Lee. Cached sufficient statistics for efficient machine
  48  * learning with large datasets. Journal of Artificial Intelligence Research 8
  49  * (1998), pp 67-91.
  50  *
  51  * =============================================================================
  52  *
  53  * The search strategy uses a combination of local and global structure search.
  54  * Similar to the technique described in:
  55  *
  56  * D. M. Chickering, D. Heckerman, and C. Meek.  A Bayesian approach to learning
  57  * Bayesian networks with local structure. In Proceedings of Thirteenth
  58  * Conference on Uncertainty in Artificial Intelligence (1997), pp. 80-89.
  59  *
  60  * =============================================================================
  61  *
  62  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  63  * of the files.
  64  *
  65  * ------------------------------------------------------------------------
  66  *
  67  * Unless otherwise noted, the following license applies to STAMP files:
  68  *
  69  * Copyright (c) 2007, Stanford University
  70  * All rights reserved.
  71  *
  72  * Redistribution and use in source and binary forms, with or without
  73  * modification, are permitted provided that the following conditions are
  74  * met:
  75 *
  76 *     * Redistributions of source code must retain the above copyright
  77 *       notice, this list of conditions and the following disclaimer.
  78 *
  79 *     * Redistributions in binary form must reproduce the above copyright
  80 *       notice, this list of conditions and the following disclaimer in
  81 *       the documentation and/or other materials provided with the
  82 *       distribution.
  83 *
  84 *     * Neither the name of Stanford University nor the names of its
  85 *       contributors may be used to endorse or promote products derived
  86 *       from this software without specific prior written permission.
  87 *
  88 * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  89 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  90 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  91 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  92 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  93 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  94 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  95 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  96 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  97 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  98 * THE POSSIBILITY OF SUCH DAMAGE.
  99 *
 100 * =============================================================================
 101 */
 102
 103
 104 #define CACHE_LINE_SIZE 64
 105 #define QUERY_VALUE_WILDCARD -1
 106 #define OPERATION_INSERT      0
 107 #define OPERATION_REMOVE      1
 108 #define OPERATION_REVERSE     2
 109 #define NUM_OPERATION         3
 110
 111 public class Learner {
 112   Adtree adtreePtr;
 113   Net netPtr;
 114   float[] localBaseLogLikelihoods;
 115   float baseLogLikelihood;
 116   LearnerTask[] tasks;
 117   List taskListPtr;
 118   int numTotalParent;
 119   int global_insertPenalty;
 120   int global_maxNumEdgeLearned;
 121   float global_operationQualityFactor;
 122
 123   public Learner() {
 124 #ifdef TEST_LEARNER
 125     global_maxNumEdgeLearned = -1;
 126     global_insertPenalty = 1;
 127     global_operationQualityFactor = 1.0F;
 128 #endif
 129   }
 130
 131   /* =============================================================================
 132    * learner_alloc
 133    * =============================================================================
 134    */
 135   public static Learner
 136     learner_alloc (Data dataPtr,
 137         Adtree adtreePtr,
 138         int numThread,
 139         int global_insertPenalty,
 140         int global_maxNumEdgeLearned,
 141         float global_operationQualityFactor)
 142     {
 143       Learner learnerPtr = new Learner();
 144
 145       if (learnerPtr != null) {
 146         learnerPtr.adtreePtr = adtreePtr;
 147         learnerPtr.netPtr = Net.net_alloc(dataPtr.numVar);
 148         learnerPtr.localBaseLogLikelihoods = new float[dataPtr.numVar];
 149         learnerPtr.baseLogLikelihood = 0.0f;
 150         learnerPtr.tasks = new LearnerTask[dataPtr.numVar];
 151         learnerPtr.taskListPtr = List.list_alloc();
 152         learnerPtr.numTotalParent = 0;
 153 #ifndef TEST_LEARNER
 154         learnerPtr.global_insertPenalty = global_insertPenalty;
 155         learnerPtr.global_maxNumEdgeLearned = global_maxNumEdgeLearned;
 156         learnerPtr.global_operationQualityFactor = global_operationQualityFactor;
 157 #endif
 158       }
 159
 160       return learnerPtr;
 161     }
 162
 163
 164   /* =============================================================================
 165    * learner_free
 166    * =============================================================================
 167    */
 168   public void
 169     learner_free ()
 170     {
 171       taskListPtr.list_free();
 172       tasks = null;
 173       localBaseLogLikelihoods = null;
 174       netPtr.net_free();
 175     }
 176
 177
 178   /* =============================================================================
 179    * computeSpecificLocalLogLikelihood
 180    * -- Query vectors should not contain wildcards
 181    * =============================================================================
 182    */
 183   public float
 184     computeSpecificLocalLogLikelihood (Adtree adtreePtr,
 185         Vector_t queryVectorPtr,
 186         Vector_t parentQueryVectorPtr)
 187     {
 188       int count = adtreePtr.adtree_getCount(queryVectorPtr);
 189       if (count == 0) {
 190         return 0.0f;
 191       }
 192
 193       double probability = (double)count / (double)adtreePtr.numRecord;
 194       int parentCount = adtreePtr.adtree_getCount(parentQueryVectorPtr);
 195
 196       if(parentCount < count || parentCount <= 0) {
 197         System.exit(0);
 198       }
 199
 200       float fval = (float)(probability * (Math.log((double)count/ (double)parentCount)));
 201
 202       return fval;
 203     }
 204
 205
 206   /* =============================================================================
 207    * createPartition
 208    * =============================================================================
 209    */
 210   public void
 211     createPartition (int min, int max, int id, int n, LocalStartStop lss)
 212     {
 213       int range = max - min;
 214       int chunk = Math.imax(1, ((range + n/2) / n)); // rounded
 215       int start = min + chunk * id;
 216       int stop;
 217       if (id == (n-1)) {
 218         stop = max;
 219       } else {
 220         stop = Math.imin(max, (start + chunk));
 221       }
 222
 223       lss.i_start = start;
 224       lss.i_stop = stop;
 225     }
 226
 227   /* =============================================================================
 228    * createTaskList
 229    * -- baseLogLikelihoods and taskListPtr are updated
 230    * =============================================================================
 231    */
 232   public static void
 233     createTaskList (int myId, int numThread, Learner learnerPtr)
 234     {
 235       boolean status;
 236
 237       Query[] queries = new Query[2];
 238       queries[0] = new Query();
 239       queries[1] = new Query();
 240
 241       Vector_t queryVectorPtr = Vector_t.vector_alloc(2);
 242       if(queryVectorPtr == null) {
 243         System.out.println("Assert failed: cannot allocate vector");
 244         System.exit(0);
 245       }
 246
 247       if((status = queryVectorPtr.vector_pushBack(queries[0])) == false) {
 248         System.out.println("Assert failed: status = "+ status + "vector_pushBack failed in createTaskList()");
 249         System.exit(0);
 250       }
 251
 252       Query parentQuery = new Query();
 253       Vector_t parentQueryVectorPtr = Vector_t.vector_alloc(1);
 254
 255       if(parentQueryVectorPtr == null) {
 256         System.out.println("Assert failed: for vector_alloc at createTaskList()");
 257         System.exit(0);
 258       }
 259
 260       int numVar = learnerPtr.adtreePtr.numVar;
 261       int numRecord = learnerPtr.adtreePtr.numRecord;
 262       float baseLogLikelihood = 0.0f;
 263       float penalty = (float)(-0.5f * Math.log((double)numRecord)); // only add 1 edge
 264
 265       LocalStartStop lss = new LocalStartStop();
 266       learnerPtr.createPartition(0, numVar, myId, numThread, lss);
 267
 268       /*
 269        * Compute base log likelihood for each variable and total base loglikelihood
 270        */
 271
 272       for (int v = lss.i_start; v < lss.i_stop; v++) {
 273
 274         float localBaseLogLikelihood = 0.0f;
 275         queries[0].index = v;
 276
 277         queries[0].value = 0;
 278         localBaseLogLikelihood +=
 279           learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 280               queryVectorPtr,
 281               parentQueryVectorPtr);
 282
 283         queries[0].value = 1;
 284         localBaseLogLikelihood +=
 285           learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 286               queryVectorPtr,
 287               parentQueryVectorPtr);
 288
 289         learnerPtr.localBaseLogLikelihoods[v] = localBaseLogLikelihood;
 290         baseLogLikelihood += localBaseLogLikelihood;
 291
 292       } // for each variable
 293
 294       atomic {
 295         float globalBaseLogLikelihood =
 296           learnerPtr.baseLogLikelihood;
 297         learnerPtr.baseLogLikelihood = (baseLogLikelihood + globalBaseLogLikelihood);
 298       }
 299
 300       /*
 301        * For each variable, find if the addition of any edge _to_ it is better
 302        */
 303
 304       if((status = parentQueryVectorPtr.vector_pushBack(parentQuery)) == false) {
 305         System.out.println("Assert failed: status = "+ status + " vector_pushBack failed in createPartition()");
 306         System.exit(0);
 307       }
 308
 309       for (int v = lss.i_start; v < lss.i_stop; v++) {
 310
 311          //Compute base log likelihood for this variable
 312
 313         queries[0].index = v;
 314         int bestLocalIndex = v;
 315         float bestLocalLogLikelihood = learnerPtr.localBaseLogLikelihoods[v];
 316
 317         if((status = queryVectorPtr.vector_pushBack(queries[1])) == false) {
 318           System.out.println("Assert failed: status = "+ status + " vector_pushBack failed in createPartition()");
 319           System.exit(0);
 320         }
 321
 322         for (int vv = 0; vv < numVar; vv++) {
 323
 324           if (vv == v) {
 325             continue;
 326           }
 327           parentQuery.index = vv;
 328           if (v < vv) {
 329             queries[0].index = v;
 330             queries[1].index = vv;
 331           } else {
 332             queries[0].index = vv;
 333             queries[1].index = v;
 334           }
 335
 336           float newLocalLogLikelihood = 0.0f;
 337
 338           queries[0].value = 0;
 339           queries[1].value = 0;
 340           parentQuery.value = 0;
 341           newLocalLogLikelihood +=
 342             learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 343                 queryVectorPtr,
 344                 parentQueryVectorPtr);
 345
 346           queries[0].value = 0;
 347           queries[1].value = 1;
 348           parentQuery.value = ((vv < v) ? 0 : 1);
 349           newLocalLogLikelihood +=
 350             learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 351                 queryVectorPtr,
 352                 parentQueryVectorPtr);
 353
 354           queries[0].value = 1;
 355           queries[1].value = 0;
 356           parentQuery.value = ((vv < v) ? 1 : 0);
 357           newLocalLogLikelihood +=
 358             learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 359                 queryVectorPtr,
 360                 parentQueryVectorPtr);
 361
 362           queries[0].value = 1;
 363           queries[1].value = 1;
 364           parentQuery.value = 1;
 365           newLocalLogLikelihood +=
 366             learnerPtr.computeSpecificLocalLogLikelihood(learnerPtr.adtreePtr,
 367                 queryVectorPtr,
 368                 parentQueryVectorPtr);
 369
 370           if (newLocalLogLikelihood > bestLocalLogLikelihood) {
 371             bestLocalIndex = vv;
 372             bestLocalLogLikelihood = newLocalLogLikelihood;
 373           }
 374
 375         } // foreach other variable
 376
 377         queryVectorPtr.vector_popBack();
 378
 379         if (bestLocalIndex != v) {
 380           float logLikelihood = numRecord * (baseLogLikelihood +
 381               + bestLocalLogLikelihood
 382               - learnerPtr.localBaseLogLikelihoods[v]);
 383           float score = penalty + logLikelihood;
 384
 385           learnerPtr.tasks[v] = new LearnerTask();
 386           LearnerTask taskPtr = learnerPtr.tasks[v];
 387           taskPtr.op = OPERATION_INSERT;
 388           taskPtr.fromId = bestLocalIndex;
 389           taskPtr.toId = v;
 390           taskPtr.score = score;
 391           atomic {
 392             status = learnerPtr.taskListPtr.list_insert(taskPtr);
 393           }
 394
 395           if(status == false) {
 396             System.out.println("Assert failed: atomic list insert failed at createTaskList()");
 397             System.exit(0);
 398           }
 399         }
 400
 401       } // for each variable
 402
 403
 404       queryVectorPtr.vector_free();
 405       parentQueryVectorPtr.vector_free();
 406
 407 #ifdef TEST_LEARNER
 408       ListNode it = learnerPtr.taskListPtr.head;
 409
 410      while (it.nextPtr!=null) {
 411         it = it.nextPtr;
 412         LearnerTask taskPtr = it.dataPtr;
 413         System.out.println("[task] op= "+ taskPtr.op +" from= "+taskPtr.fromId+" to= " +taskPtr.toId+
 414            " score= " + taskPtr.score);
 415       }
 416 #endif // TEST_LEARNER
 417
 418     }
 419
 420   /* =============================================================================
 421    * TMpopTask
 422    * -- Returns null is list is empty
 423    * =============================================================================
 424    */
 425   public LearnerTask TMpopTask (List taskListPtr)
 426     {
 427       LearnerTask taskPtr = null;
 428
 429       ListNode it = taskListPtr.head;
 430       if (it.nextPtr!=null) {
 431         it = it.nextPtr;
 432         taskPtr = it.dataPtr;
 433         boolean status = taskListPtr.list_remove(taskPtr);
 434         if(status == false) {
 435           System.out.println("Assert failed: when removing from a list in TMpopTask()");
 436           System.exit(0);
 437         }
 438       }
 439
 440       return taskPtr;
 441     }
 442
 443
 444   /* =============================================================================
 445    * populateParentQuery
 446    * -- Modifies contents of parentQueryVectorPtr
 447    * =============================================================================
 448    */
 449   public void
 450     populateParentQueryVector (Net netPtr,
 451         int id,
 452         Query[] queries,
 453         Vector_t parentQueryVectorPtr)
 454     {
 455       parentQueryVectorPtr.vector_clear();
 456
 457       IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id);
 458       IntListNode it = parentIdListPtr.head;
 459       while (it.nextPtr!=null) {
 460         it = it.nextPtr;
 461         int parentId = it.dataPtr;
 462         boolean status = parentQueryVectorPtr.vector_pushBack(queries[parentId]);
 463         if(status == false) {
 464           System.out.println("Assert failed: unable to pushBack in queue");
 465           System.exit(0);
 466         }
 467       }
 468     }
 469
 470
 471   /* =============================================================================
 472    * TMpopulateParentQuery
 473    * -- Modifies contents of parentQueryVectorPtr
 474    * =============================================================================
 475    */
 476   public void
 477     TMpopulateParentQueryVector (Net netPtr,
 478         int id,
 479         Query[] queries,
 480         Vector_t parentQueryVectorPtr)
 481     {
 482       parentQueryVectorPtr.vector_clear();
 483
 484       IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id);
 485       IntListNode it = parentIdListPtr.head;
 486
 487       while (it.nextPtr!=null) {
 488         it = it.nextPtr;
 489         int parentId = it.dataPtr;
 490         boolean status = parentQueryVectorPtr.vector_pushBack(queries[parentId]);
 491         if(status == false) {
 492           System.out.println("Assert failed: unable to pushBack in queue in TMpopulateParentQueryVector()");
 493           System.exit(0);
 494         }
 495       }
 496     }
 497
 498
 499   /* =============================================================================
 500    * populateQueryVectors
 501    * -- Modifies contents of queryVectorPtr and parentQueryVectorPtr
 502    * =============================================================================
 503    */
 504   public void
 505     populateQueryVectors (Net netPtr,
 506         int id,
 507         Query[] queries,
 508         Vector_t queryVectorPtr,
 509         Vector_t parentQueryVectorPtr)
 510     {
 511       populateParentQueryVector(netPtr, id, queries, parentQueryVectorPtr);
 512
 513       boolean status;
 514       status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr);
 515       if(status == false ) {
 516         System.out.println("Assert failed: while vector copy in populateQueryVectors()");
 517         System.exit(0);
 518       }
 519
 520       status = queryVectorPtr.vector_pushBack(queries[id]);
 521       if(status == false ) {
 522         System.out.println("Assert failed: while vector pushBack in populateQueryVectors()");
 523         System.exit(0);
 524       }
 525
 526       queryVectorPtr.vector_sort();
 527     }
 528
 529
 530   /* =============================================================================
 531    * TMpopulateQueryVectors
 532    * -- Modifies contents of queryVectorPtr and parentQueryVectorPtr
 533    * =============================================================================
 534    */
 535   public void
 536     TMpopulateQueryVectors (Net netPtr,
 537         int id,
 538         Query[] queries,
 539         Vector_t queryVectorPtr,
 540         Vector_t parentQueryVectorPtr)
 541     {
 542       TMpopulateParentQueryVector(netPtr, id, queries, parentQueryVectorPtr);
 543
 544       boolean status;
 545       status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr);
 546       if(status == false ) {
 547         System.out.println("Assert failed: while vector copy in TMpopulateQueryVectors()");
 548         System.exit(0);
 549       }
 550       status = queryVectorPtr.vector_pushBack(queries[id]);
 551       if(status == false ) {
 552         System.out.println("Assert failed: while vector pushBack in TMpopulateQueryVectors()");
 553         System.exit(0);
 554       }
 555
 556       queryVectorPtr.vector_sort();
 557     }
 558
 559   /* =============================================================================
 560    * computeLocalLogLikelihoodHelper
 561    * -- Recursive helper routine
 562    * =============================================================================
 563    */
 564   public float
 565     computeLocalLogLikelihoodHelper (int i,
 566         int numParent,
 567         Adtree adtreePtr,
 568         Query[] queries,
 569         Vector_t queryVectorPtr,
 570         Vector_t parentQueryVectorPtr)
 571     {
 572       if (i >= numParent) {
 573         return computeSpecificLocalLogLikelihood(adtreePtr,
 574             queryVectorPtr,
 575             parentQueryVectorPtr);
 576       }
 577
 578       float localLogLikelihood = 0.0f;
 579
 580       Query parentQueryPtr = (Query) (parentQueryVectorPtr.vector_at(i));
 581       int parentIndex = parentQueryPtr.index;
 582
 583       queries[parentIndex].value = 0;
 584       localLogLikelihood += computeLocalLogLikelihoodHelper((i + 1),
 585           numParent,
 586           adtreePtr,
 587           queries,
 588           queryVectorPtr,
 589           parentQueryVectorPtr);
 590
 591       queries[parentIndex].value = 1;
 592       localLogLikelihood += computeLocalLogLikelihoodHelper((i + 1),
 593           numParent,
 594           adtreePtr,
 595           queries,
 596           queryVectorPtr,
 597           parentQueryVectorPtr);
 598
 599       queries[parentIndex].value = QUERY_VALUE_WILDCARD;
 600
 601       return localLogLikelihood;
 602     }
 603
 604
 605   /* =============================================================================
 606    * computeLocalLogLikelihood
 607    * -- Populate the query vectors before passing as args
 608    * =============================================================================
 609    */
 610   public float
 611     computeLocalLogLikelihood (int id,
 612         Adtree adtreePtr,
 613         Net netPtr,
 614         Query[] queries,
 615         Vector_t queryVectorPtr,
 616         Vector_t parentQueryVectorPtr)
 617     {
 618       int numParent = parentQueryVectorPtr.vector_getSize();
 619       float localLogLikelihood = 0.0f;
 620
 621       queries[id].value = 0;
 622       localLogLikelihood += computeLocalLogLikelihoodHelper(0,
 623           numParent,
 624           adtreePtr,
 625           queries,
 626           queryVectorPtr,
 627           parentQueryVectorPtr);
 628
 629       queries[id].value = 1;
 630       localLogLikelihood += computeLocalLogLikelihoodHelper(0,
 631           numParent,
 632           adtreePtr,
 633           queries,
 634           queryVectorPtr,
 635           parentQueryVectorPtr);
 636
 637       queries[id].value = QUERY_VALUE_WILDCARD;
 638
 639       return localLogLikelihood;
 640     }
 641
 642
 643   /* =============================================================================
 644    * TMfindBestInsertTask
 645    * =============================================================================
 646    */
 647   public LearnerTask
 648     TMfindBestInsertTask (FindBestTaskArg argPtr)
 649     {
 650       int       toId                      = argPtr.toId;
 651       Learner   learnerPtr                = argPtr.learnerPtr;
 652       Query[]   queries                   = argPtr.queries;
 653       Vector_t  queryVectorPtr            = argPtr.queryVectorPtr;
 654       Vector_t  parentQueryVectorPtr      = argPtr.parentQueryVectorPtr;
 655       int       numTotalParent            = argPtr.numTotalParent;
 656       float     basePenalty               = argPtr.basePenalty;
 657       float     baseLogLikelihood         = argPtr.baseLogLikelihood;
 658       BitMap    invalidBitmapPtr          = argPtr.bitmapPtr;
 659       Queue     workQueuePtr              = argPtr.workQueuePtr;
 660       Vector_t  baseParentQueryVectorPtr  = argPtr.aQueryVectorPtr;
 661       Vector_t  baseQueryVectorPtr        = argPtr.bQueryVectorPtr;
 662
 663       boolean status;
 664       Adtree adtreePtr               = learnerPtr.adtreePtr;
 665       Net    netPtr                  = learnerPtr.netPtr;
 666
 667       TMpopulateParentQueryVector(netPtr, toId, queries, parentQueryVectorPtr);
 668
 669       /*
 670        * Create base query and parentQuery
 671        */
 672
 673       status = Vector_t.vector_copy(baseParentQueryVectorPtr, parentQueryVectorPtr);
 674       if(status == false) {
 675         System.out.println("Assert failed: copying baseParentQuery vector in TMfindBestInsertTask");
 676         System.exit(0);
 677       }
 678
 679       status = Vector_t.vector_copy(baseQueryVectorPtr, baseParentQueryVectorPtr);
 680       if(status == false) {
 681         System.out.println("Assert failed: copying baseQuery vector in TMfindBestInsertTask");
 682         System.exit(0);
 683       }
 684
 685       status = baseQueryVectorPtr.vector_pushBack(queries[toId]);
 686       if(status == false ) {
 687         System.out.println("Assert failed: while vector pushBack in TMfindBestInsertTask()");
 688         System.exit(0);
 689       }
 690
 691       queryVectorPtr.vector_sort();
 692
 693       /*
 694        * Search all possible valid operations for better local log likelihood
 695        */
 696
 697       int bestFromId = toId; // flag for not found
 698       float oldLocalLogLikelihood = learnerPtr.localBaseLogLikelihoods[toId];
 699       float bestLocalLogLikelihood = oldLocalLogLikelihood;
 700
 701       status = netPtr.net_findDescendants(toId, invalidBitmapPtr, workQueuePtr);
 702       if(status == false) {
 703         System.out.println("Assert failed: while net_findDescendants in TMfindBestInsertTask()");
 704         System.exit(0);
 705       }
 706
 707       int fromId = -1;
 708
 709       IntList parentIdListPtr = netPtr.net_getParentIdListPtr(toId);
 710
 711       int maxNumEdgeLearned = global_maxNumEdgeLearned;
 712
 713       if ((maxNumEdgeLearned < 0) ||
 714           (parentIdListPtr.list_getSize() <= maxNumEdgeLearned))
 715       {
 716
 717         IntListNode it = parentIdListPtr.head;
 718
 719         while(it.nextPtr!=null) {
 720           it = it.nextPtr;
 721           int parentId = it.dataPtr;
 722           invalidBitmapPtr.bitmap_set(parentId); // invalid since already have edge
 723         }
 724
 725         while ((fromId = invalidBitmapPtr.bitmap_findClear((fromId + 1))) >= 0) {
 726
 727           if (fromId == toId) {
 728             continue;
 729           }
 730
 731           status = Vector_t.vector_copy(queryVectorPtr, baseQueryVectorPtr);
 732           if(status == false) {
 733             System.out.println("Assert failed: copying query vector in TMfindBestInsertTask");
 734             System.exit(0);
 735           }
 736
 737           status = queryVectorPtr.vector_pushBack(queries[fromId]);
 738           if(status == false) {
 739             System.out.println("Assert failed: vector pushback for query in TMfindBestInsertTask");
 740             System.exit(0);
 741           }
 742
 743           queryVectorPtr.vector_sort();
 744
 745           status = Vector_t.vector_copy(parentQueryVectorPtr, baseParentQueryVectorPtr);
 746           if(status == false) {
 747             System.out.println("Assert failed: copying parentQuery vector in TMfindBestInsertTask");
 748             System.exit(0);
 749           }
 750
 751           status = parentQueryVectorPtr.vector_pushBack(queries[fromId]);
 752           if(status == false) {
 753             System.out.println("Assert failed: vector pushBack for parentQuery in TMfindBestInsertTask");
 754             System.exit(0);
 755           }
 756
 757           parentQueryVectorPtr.vector_sort();
 758
 759           float newLocalLogLikelihood =
 760             computeLocalLogLikelihood(toId,
 761                 adtreePtr,
 762                 netPtr,
 763                 queries,
 764                 queryVectorPtr,
 765                 parentQueryVectorPtr);
 766
 767           if (newLocalLogLikelihood > bestLocalLogLikelihood) {
 768             bestLocalLogLikelihood = newLocalLogLikelihood;
 769             bestFromId = fromId;
 770           }
 771
 772         } // foreach valid parent
 773
 774       } // if have not exceeded max number of edges to learn
 775
 776       /*
 777        * Return best task; Note: if none is better, fromId will equal toId
 778        */
 779
 780       LearnerTask bestTask = new LearnerTask();
 781       bestTask.op     = OPERATION_INSERT;
 782       bestTask.fromId = bestFromId;
 783       bestTask.toId   = toId;
 784       bestTask.score  = 0.0f;
 785
 786       if (bestFromId != toId) {
 787         int numRecord = adtreePtr.numRecord;
 788         int numParent = parentIdListPtr.list_getSize() + 1;
 789         float penalty =
 790           (numTotalParent + numParent * global_insertPenalty) * basePenalty;
 791         float logLikelihood = numRecord * (baseLogLikelihood +
 792             + bestLocalLogLikelihood
 793             - oldLocalLogLikelihood);
 794         float bestScore = penalty + logLikelihood;
 795         bestTask.score  = bestScore;
 796       }
 797
 798       return bestTask;
 799     }
 800
 801 #ifdef LEARNER_TRY_REMOVE
 802   /* =============================================================================
 803    * TMfindBestRemoveTask
 804    * =============================================================================
 805    */
 806   public LearnerTask
 807     TMfindBestRemoveTask (FindBestTaskArg argPtr)
 808     {
 809       int       toId                     = argPtr.toId;
 810       Learner   learnerPtr               = argPtr.learnerPtr;
 811       Query[]   queries                  = argPtr.queries;
 812       Vector_t  queryVectorPtr           = argPtr.queryVectorPtr;
 813       Vector_t  parentQueryVectorPtr     = argPtr.parentQueryVectorPtr;
 814       int       numTotalParent           = argPtr.numTotalParent;
 815       float     basePenalty              = argPtr.basePenalty;
 816       float     baseLogLikelihood        = argPtr.baseLogLikelihood;
 817       Vector_t  origParentQueryVectorPtr = argPtr.aQueryVectorPtr;
 818
 819       boolean status;
 820       Adtree adtreePtr = learnerPtr.adtreePtr;
 821       Net netPtr = learnerPtr.netPtr;
 822       float[] localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods;
 823
 824       TMpopulateParentQueryVector(netPtr, toId, queries, origParentQueryVectorPtr);
 825       int numParent = origParentQueryVectorPtr.vector_getSize();
 826
 827       /*
 828        * Search all possible valid operations for better local log likelihood
 829        */
 830
 831       int bestFromId = toId; // flag for not found
 832       float oldLocalLogLikelihood = localBaseLogLikelihoods[toId];
 833       float bestLocalLogLikelihood = oldLocalLogLikelihood;
 834
 835       int i;
 836       for (i = 0; i < numParent; i++) {
 837
 838         Query queryPtr = (Query) (origParentQueryVectorPtr.vector_at(i));
 839         int fromId = queryPtr.index;
 840
 841         /*
 842          * Create parent query (subset of parents since remove an edge)
 843          */
 844
 845         parentQueryVectorPtr.vector_clear();
 846
 847         for (int p = 0; p < numParent; p++) {
 848           if (p != fromId) {
 849             Query tmpqueryPtr = (Query) (origParentQueryVectorPtr.vector_at(p));
 850             status = parentQueryVectorPtr.vector_pushBack(queries[tmpqueryPtr.index]);
 851             if(status == false) {
 852               System.out.println("Assert failed: vector_pushBack to parentQuery in TMfindBestRemoveTask()");
 853               System.exit(0);
 854             }
 855           }
 856         } // create new parent query
 857
 858         /*
 859          * Create query
 860          */
 861
 862         status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr);
 863         if(status == false) {
 864           System.out.println("Assert failed: while vector copy to query in TMfindBestRemoveTask()");
 865           System.exit(0);
 866         }
 867
 868         status = queryVectorPtr.vector_pushBack(queries[toId]);
 869         if(status == false) {
 870           System.out.println("Assert failed: while vector_pushBack to query in TMfindBestRemoveTask()");
 871           System.exit(0);
 872         }
 873
 874         queryVectorPtr.vector_sort();
 875
 876         /*
 877          * See if removing parent is better
 878          */
 879
 880         float newLocalLogLikelihood =
 881           computeLocalLogLikelihood(toId,
 882               adtreePtr,
 883               netPtr,
 884               queries,
 885               queryVectorPtr,
 886               parentQueryVectorPtr);
 887
 888         if (newLocalLogLikelihood > bestLocalLogLikelihood) {
 889           bestLocalLogLikelihood = newLocalLogLikelihood;
 890           bestFromId = fromId;
 891         }
 892
 893       } // for each parent
 894
 895       /*
 896        * Return best task; Note: if none is better, fromId will equal toId
 897        */
 898
 899       LearnerTask bestTask = new LearnerTask();
 900       bestTask.op     = OPERATION_REMOVE;
 901       bestTask.fromId = bestFromId;
 902       bestTask.toId   = toId;
 903       bestTask.score  = 0.0f;
 904
 905       if (bestFromId != toId) {
 906         int numRecord = adtreePtr.numRecord;
 907         float penalty = (numTotalParent - 1) * basePenalty;
 908         float logLikelihood = numRecord * (baseLogLikelihood +
 909             + bestLocalLogLikelihood
 910             - oldLocalLogLikelihood);
 911         float bestScore = penalty + logLikelihood;
 912         bestTask.score  = bestScore;
 913       }
 914
 915       return bestTask;
 916     }
 917 #endif /* LEARNER_TRY_REMOVE */
 918
 919
 920 #ifdef LEARNER_TRY_REVERSE
 921   /* =============================================================================
 922    * TMfindBestReverseTask
 923    * =============================================================================
 924    */
 925   public LearnerTask
 926     TMfindBestReverseTask (FindBestTaskArg argPtr)
 927     {
 928       int       toId                         = argPtr.toId;
 929       Learner   learnerPtr                   = argPtr.learnerPtr;
 930       Query[]   queries                      = argPtr.queries;
 931       Vector_t  queryVectorPtr               = argPtr.queryVectorPtr;
 932       Vector_t  parentQueryVectorPtr         = argPtr.parentQueryVectorPtr;
 933       int       numTotalParent               = argPtr.numTotalParent;
 934       float     basePenalty                  = argPtr.basePenalty;
 935       float     baseLogLikelihood            = argPtr.baseLogLikelihood;
 936       BitMap    visitedBitmapPtr             = argPtr.bitmapPtr;
 937       Queue     workQueuePtr                 = argPtr.workQueuePtr;
 938       Vector_t  toOrigParentQueryVectorPtr   = argPtr.aQueryVectorPtr;
 939       Vector_t  fromOrigParentQueryVectorPtr = argPtr.bQueryVectorPtr;
 940
 941       boolean status;
 942       Adtree adtreePtr = learnerPtr.adtreePtr;
 943       Net netPtr = learnerPtr.netPtr;
 944       float[] localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods;
 945
 946       TMpopulateParentQueryVector(netPtr, toId, queries, toOrigParentQueryVectorPtr);
 947       int numParent = toOrigParentQueryVectorPtr.vector_getSize();
 948
 949       /*
 950        * Search all possible valid operations for better local log likelihood
 951        */
 952
 953       int bestFromId = toId; // flag for not found
 954       float oldLocalLogLikelihood = localBaseLogLikelihoods[toId];
 955       float bestLocalLogLikelihood = oldLocalLogLikelihood;
 956       int fromId = 0;
 957
 958       for (int i = 0; i < numParent; i++) {
 959
 960         Query queryPtr = (Query) (toOrigParentQueryVectorPtr.vector_at(i));
 961         fromId = queryPtr.index;
 962
 963         bestLocalLogLikelihood =
 964           oldLocalLogLikelihood + localBaseLogLikelihoods[fromId];
 965
 966         TMpopulateParentQueryVector(netPtr,
 967             fromId,
 968             queries,
 969             fromOrigParentQueryVectorPtr);
 970
 971         /*
 972          * Create parent query (subset of parents since remove an edge)
 973          */
 974
 975         parentQueryVectorPtr.vector_clear();
 976
 977         for (int p = 0; p < numParent; p++) {
 978           if (p != fromId) {
 979             Query tmpqueryPtr = (Query) (toOrigParentQueryVectorPtr.vector_at(p));
 980             status = parentQueryVectorPtr.vector_pushBack(queries[tmpqueryPtr.index]);
 981             if(status == false) {
 982               System.out.println("Assert failed: while vector_pushBack parentQueryVectorPtr");
 983               System.exit(0);
 984             }
 985           }
 986         } // create new parent query
 987
 988         /*
 989          * Create query
 990          */
 991
 992         status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr);
 993         if(status == false) {
 994           System.out.println("Assert failed: while vector_copy in TMfindBestReverseTask()");
 995           System.exit(0);
 996         }
 997
 998         status = queryVectorPtr.vector_pushBack(queries[toId]);
 999         if(status == false) {
1000           System.out.println("Assert failed: while vector_pushBack in TMfindBestReverseTask()");
1001           System.exit(0);
1002         }
1003
1004         queryVectorPtr.vector_sort();
1005
1006         /*
1007          * Get log likelihood for removing parent from toId
1008          */
1009
1010         float newLocalLogLikelihood =
1011           computeLocalLogLikelihood(toId,
1012               adtreePtr,
1013               netPtr,
1014               queries,
1015               queryVectorPtr,
1016               parentQueryVectorPtr);
1017
1018         /*
1019          * Get log likelihood for adding parent to fromId
1020          */
1021
1022         status = Vector_t.vector_copy(parentQueryVectorPtr, fromOrigParentQueryVectorPtr);
1023         if(status == false) {
1024           System.out.println("Assert failed: while parentQuery vector_copy in TMfindBestReverseTask()");
1025           System.exit(0);
1026         }
1027
1028         status = parentQueryVectorPtr.vector_pushBack(queries[toId]);
1029         if(status == false) {
1030           System.out.println("Assert failed: while vector_pushBack into parentQuery on TMfindBestReverseTask()");
1031           System.exit(0);
1032         }
1033
1034         parentQueryVectorPtr.vector_sort();
1035
1036         status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr);
1037         if(status == false) {
1038           System.out.println("Assert failed: while vector_copy on TMfindBestReverseTask()");
1039           System.exit(0);
1040         }
1041
1042         status = queryVectorPtr.vector_pushBack(queries[fromId]);
1043         if(status == false) {
1044           System.out.println("Assert failed: while vector_pushBack on TMfindBestReverseTask()");
1045           System.exit(0);
1046         }
1047
1048         queryVectorPtr.vector_sort();
1049
1050         newLocalLogLikelihood +=
1051           computeLocalLogLikelihood(fromId,
1052               adtreePtr,
1053               netPtr,
1054               queries,
1055               queryVectorPtr,
1056               parentQueryVectorPtr);
1057
1058         /*
1059          * Record best
1060          */
1061
1062         if (newLocalLogLikelihood > bestLocalLogLikelihood) {
1063           bestLocalLogLikelihood = newLocalLogLikelihood;
1064           bestFromId = fromId;
1065         }
1066
1067       } // for each parent
1068
1069       /*
1070        * Check validity of best
1071        */
1072
1073       if (bestFromId != toId) {
1074         boolean isTaskValid = true;
1075         netPtr.net_applyOperation(OPERATION_REMOVE, bestFromId, toId);
1076         if (netPtr.net_isPath(bestFromId,
1077               toId,
1078               visitedBitmapPtr,
1079               workQueuePtr))
1080         {
1081           isTaskValid = false;
1082         }
1083         netPtr.net_applyOperation(OPERATION_INSERT, bestFromId, toId);
1084         if (!isTaskValid) {
1085           bestFromId = toId;
1086         }
1087       }
1088
1089       /*
1090        * Return best task; Note: if none is better, fromId will equal toId
1091        */
1092
1093       LearnerTask bestTask = new LearnerTask();
1094       bestTask.op     = OPERATION_REVERSE;
1095       bestTask.fromId = bestFromId;
1096       bestTask.toId   = toId;
1097       bestTask.score  = 0.0f;
1098
1099       if (bestFromId != toId) {
1100         float fromLocalLogLikelihood = localBaseLogLikelihoods[bestFromId];
1101         int numRecord = adtreePtr.numRecord;
1102         float penalty = numTotalParent * basePenalty;
1103         float logLikelihood = numRecord * (baseLogLikelihood +
1104             + bestLocalLogLikelihood
1105             - oldLocalLogLikelihood
1106             - fromLocalLogLikelihood);
1107         float bestScore = penalty + logLikelihood;
1108         bestTask.score  = bestScore;
1109       }
1110
1111       return bestTask;
1112     }
1113
1114 #endif /* LEARNER_TRY_REVERSE */
1115
1116
1117   /* =============================================================================
1118    * learnStructure
1119    *
1120    * Note it is okay if the score is not exact, as we are relaxing the greedy
1121    * search. This means we do not need to communicate baseLogLikelihood across
1122    * threads.
1123    * =============================================================================
1124    */
1125   public static void
1126     learnStructure (int myId, int numThread, Learner learnerPtr)
1127     {
1128
1129       int numRecord = learnerPtr.adtreePtr.numRecord;
1130
1131       float operationQualityFactor = learnerPtr.global_operationQualityFactor;
1132
1133       BitMap visitedBitmapPtr = BitMap.bitmap_alloc(learnerPtr.adtreePtr.numVar);
1134       if(visitedBitmapPtr == null) {
1135         System.out.println("Assert failed: for bitmap alloc in learnStructure()");
1136         System.exit(0);
1137       }
1138
1139       Queue workQueuePtr = Queue.queue_alloc(-1);
1140       if(workQueuePtr == null) {
1141         System.out.println("Assert failed: for vector alloc in learnStructure()");
1142         System.exit(0);
1143       }
1144
1145       int numVar = learnerPtr.adtreePtr.numVar;
1146       Query[] queries = new Query[numVar];
1147
1148       if(queries == null) {
1149         System.out.println("Assert failed: for queries alloc in learnStructure()");
1150         System.exit(0);
1151       }
1152
1153       for (int v = 0; v < numVar; v++) {
1154         queries[v] = new Query();
1155         queries[v].index = v;
1156         queries[v].value = QUERY_VALUE_WILDCARD;
1157       }
1158
1159       float basePenalty = (float)(-0.5 * Math.log((double)numRecord));
1160
1161       Vector_t queryVectorPtr = Vector_t.vector_alloc(1);
1162       if(queryVectorPtr == null) {
1163         System.out.println("Assert failed: for vector_alloc in learnStructure()");
1164         System.exit(0);
1165       }
1166
1167       Vector_t parentQueryVectorPtr = Vector_t.vector_alloc(1);
1168       if(parentQueryVectorPtr == null) {
1169         System.out.println("Assert failed: for vector_alloc in learnStructure()");
1170         System.exit(0);
1171       }
1172
1173       Vector_t aQueryVectorPtr = Vector_t.vector_alloc(1);
1174       if(aQueryVectorPtr == null) {
1175         System.out.println("Assert failed: for vector_alloc in learnStructure()");
1176         System.exit(0);
1177       }
1178
1179       Vector_t bQueryVectorPtr = Vector_t.vector_alloc(1);
1180       if(bQueryVectorPtr == null) {
1181         System.out.println("Assert failed: for vector_alloc in learnStructure()");
1182         System.exit(0);
1183       }
1184
1185
1186       FindBestTaskArg arg = new FindBestTaskArg();
1187       arg.learnerPtr           = learnerPtr;
1188       arg.queries              = queries;
1189       arg.queryVectorPtr       = queryVectorPtr;
1190       arg.parentQueryVectorPtr = parentQueryVectorPtr;
1191       arg.bitmapPtr            = visitedBitmapPtr;
1192       arg.workQueuePtr         = workQueuePtr;
1193       arg.aQueryVectorPtr      = aQueryVectorPtr;
1194       arg.bQueryVectorPtr      = bQueryVectorPtr;
1195
1196       while (true) {
1197
1198         LearnerTask taskPtr;
1199
1200         atomic {
1201           taskPtr = learnerPtr.TMpopTask(learnerPtr.taskListPtr);
1202         }
1203
1204         if (taskPtr == null) {
1205           break;
1206         }
1207
1208         int op = taskPtr.op;
1209         int fromId = taskPtr.fromId;
1210         int toId = taskPtr.toId;
1211
1212         boolean isTaskValid;
1213
1214         atomic {
1215           /*
1216            * Check if task is still valid
1217            */
1218
1219           isTaskValid = true;
1220           if(op == OPERATION_INSERT) {
1221             if(learnerPtr.netPtr.net_hasEdge(fromId, toId) ||
1222                 learnerPtr.netPtr.net_isPath(toId,
1223                   fromId,
1224                   visitedBitmapPtr,
1225                   workQueuePtr))
1226             {
1227               isTaskValid = false;
1228             }
1229           } else if (op == OPERATION_REMOVE) {
1230             // Can never create cycle, so always valid
1231             ;
1232           } else if (op == OPERATION_REVERSE) {
1233             // Temporarily remove edge for check
1234             learnerPtr.netPtr.net_applyOperation(OPERATION_REMOVE, fromId, toId);
1235             if(learnerPtr.netPtr.net_isPath(fromId,
1236                   toId,
1237                   visitedBitmapPtr,
1238                   workQueuePtr))
1239             {
1240               isTaskValid = false;
1241             }
1242             learnerPtr.netPtr.net_applyOperation(OPERATION_INSERT, fromId, toId);
1243           } else {
1244             System.out.println("Assert failed: We shouldn't get here in learnStructure()");
1245             System.exit(0);
1246           }
1247
1248
1249 #ifdef TEST_LEARNER
1250           System.out.println("[task] op= " + taskPtr.op + " from= " + taskPtr.fromId + " to= " +
1251               taskPtr.toId + " score= " + taskPtr.score + " valid= " + (isTaskValid ? "yes" : "no"));
1252 #endif
1253
1254           /*
1255            * Perform task: update graph and probabilities
1256            */
1257
1258           if (isTaskValid) {
1259             learnerPtr.netPtr.net_applyOperation(op, fromId, toId);
1260           }
1261
1262         }
1263
1264         float deltaLogLikelihood = 0.0f;
1265
1266         if (isTaskValid) {
1267           float newBaseLogLikelihood;
1268           if(op == OPERATION_INSERT) {
1269             atomic {
1270               learnerPtr.TMpopulateQueryVectors(learnerPtr.netPtr,
1271                                                 toId,
1272                                                 queries,
1273                                                 queryVectorPtr,
1274                                                 parentQueryVectorPtr);
1275               newBaseLogLikelihood =
1276                 learnerPtr.computeLocalLogLikelihood(toId,
1277                                                 learnerPtr.adtreePtr,
1278                                                 learnerPtr.netPtr,
1279                                                 queries,
1280                                                 queryVectorPtr,
1281                                                 parentQueryVectorPtr);
1282               float toLocalBaseLogLikelihood = learnerPtr.localBaseLogLikelihoods[toId];
1283               deltaLogLikelihood +=
1284                 toLocalBaseLogLikelihood - newBaseLogLikelihood;
1285               learnerPtr.localBaseLogLikelihoods[toId] = newBaseLogLikelihood;
1286             }
1287
1288             atomic {
1289               int numTotalParent = learnerPtr.numTotalParent;
1290               learnerPtr.numTotalParent = numTotalParent + 1;
1291             }
1292
1293 #ifdef LEARNER_TRY_REMOVE
1294           } else if(op == OPERATION_REMOVE) {
1295             atomic {
1296               learnerPtr.TMpopulateQueryVectors(learnerPtr.netPtr,
1297                                                 fromId,
1298                                                 queries,
1299                                                 queryVectorPtr,
1300                                                 parentQueryVectorPtr);
1301               newBaseLogLikelihood =
1302                 learnerPtr. computeLocalLogLikelihood(fromId,
1303                                               learnerPtr.adtreePtr,
1304                                               learnerPtr.netPtr,
1305                                               queries,
1306                                               queryVectorPtr,
1307                                               parentQueryVectorPtr);
1308               float fromLocalBaseLogLikelihood =
1309                     learnerPtr.localBaseLogLikelihoods[fromId];
1310               deltaLogLikelihood +=
1311                     fromLocalBaseLogLikelihood - newBaseLogLikelihood;
1312               learnerPtr.localBaseLogLikelihoods[fromId] = newBaseLogLikelihood;
1313             }
1314
1315             atomic{
1316               int numTotalParent = learnerPtr.numTotalParent;
1317               learnerPtr.numTotalParent = numTotalParent - 1;
1318             }
1319
1320 #endif // LEARNER_TRY_REMOVE
1321 #ifdef LEARNER_TRY_REVERSE
1322           } else if(op == OPERATION_REVERSE) {
1323             atomic {
1324               learnerPtr.TMpopulateQueryVectors(learnerPtr.netPtr,
1325                                                 fromId,
1326                                                 queries,
1327                                                 queryVectorPtr,
1328                                                 parentQueryVectorPtr);
1329               newBaseLogLikelihood =
1330                 learnerPtr.computeLocalLogLikelihood(fromId,
1331                                         learnerPtr.adtreePtr,
1332                                         learnerPtr.netPtr,
1333                                         queries,
1334                                         queryVectorPtr,
1335                                         parentQueryVectorPtr);
1336               float fromLocalBaseLogLikelihood =
1337                           learnerPtr.localBaseLogLikelihoods[fromId];
1338               deltaLogLikelihood +=
1339                 fromLocalBaseLogLikelihood - newBaseLogLikelihood;
1340               learnerPtr.localBaseLogLikelihoods[fromId] = newBaseLogLikelihood;
1341             }
1342
1343             atomic {
1344               learnerPtr.TMpopulateQueryVectors(learnerPtr.netPtr,
1345                                                 toId,
1346                                                 queries,
1347                                                 queryVectorPtr,
1348                                                 parentQueryVectorPtr);
1349               newBaseLogLikelihood =
1350                 learnerPtr.computeLocalLogLikelihood(toId,
1351                                         learnerPtr.adtreePtr,
1352                                         learnerPtr.netPtr,
1353                                         queries,
1354                                         queryVectorPtr,
1355                                         parentQueryVectorPtr);
1356               float toLocalBaseLogLikelihood =
1357                         learnerPtr.localBaseLogLikelihoods[toId];
1358               deltaLogLikelihood +=
1359                 toLocalBaseLogLikelihood - newBaseLogLikelihood;
1360               learnerPtr.localBaseLogLikelihoods[toId] = newBaseLogLikelihood;
1361             }
1362
1363 #endif // LEARNER_TRY_REVERSE
1364           } else {
1365             System.out.println("Assert failed: We should not reach here in learnerPtr()");
1366             System.exit(0);
1367           } //switch op
1368
1369         } //if isTaskValid
1370
1371         /*
1372          * Update/read globals
1373          */
1374
1375         float baseLogLikelihood;
1376         int numTotalParent;
1377
1378         atomic {
1379           float oldBaseLogLikelihood = learnerPtr.baseLogLikelihood;
1380           float newBaseLogLikelihood = oldBaseLogLikelihood + deltaLogLikelihood;
1381           learnerPtr.baseLogLikelihood = newBaseLogLikelihood;
1382           baseLogLikelihood = newBaseLogLikelihood;
1383           numTotalParent = learnerPtr.numTotalParent;
1384         }
1385
1386         /*
1387          * Find next task
1388          */
1389
1390
1391         float baseScore = ((float)numTotalParent * basePenalty)
1392           + (numRecord * baseLogLikelihood);
1393
1394         LearnerTask bestTask = new LearnerTask();
1395         bestTask.op     = NUM_OPERATION;
1396         bestTask.toId   = -1;
1397         bestTask.fromId = -1;
1398         bestTask.score  = baseScore;
1399
1400         LearnerTask newTask = new LearnerTask();
1401
1402         arg.toId              = toId;
1403         arg.numTotalParent    = numTotalParent;
1404         arg.basePenalty       = basePenalty;
1405         arg.baseLogLikelihood = baseLogLikelihood;
1406
1407         atomic {
1408           newTask = learnerPtr.TMfindBestInsertTask(arg);
1409         }
1410
1411         if ((newTask.fromId != newTask.toId) &&
1412             (newTask.score > (bestTask.score / operationQualityFactor)))
1413         {
1414           bestTask = newTask;
1415         }
1416
1417 #ifdef LEARNER_TRY_REMOVE
1418         atomic {
1419           newTask = learnerPtr.TMfindBestRemoveTask(arg);
1420         }
1421
1422         if ((newTask.fromId != newTask.toId) &&
1423             (newTask.score > (bestTask.score / operationQualityFactor)))
1424         {
1425           bestTask = newTask;
1426         }
1427 #endif // LEARNER_TRY_REMOVE
1428
1429 #ifdef LEARNER_TRY_REVERSE
1430         atomic {
1431           newTask = learnerPtr.TMfindBestReverseTask(arg);
1432         }
1433
1434         if ((newTask.fromId != newTask.toId) &&
1435             (newTask.score > (bestTask.score / operationQualityFactor)))
1436         {
1437           bestTask = newTask;
1438         }
1439 #endif // LEARNER_TRY_REVERSE
1440
1441         if (bestTask.toId != -1) {
1442           LearnerTask[] tasks = learnerPtr.tasks;
1443           tasks[toId] = bestTask;
1444           atomic {
1445             learnerPtr.taskListPtr.list_insert(tasks[toId]);
1446           }
1447 #ifdef TEST_LEARNER
1448           System.out.println("[new]  op= " + bestTask.op + " from= "+ bestTask.fromId + " to= "+ bestTask.toId +
1449               " score= " + bestTask.score);
1450 #endif
1451         }
1452
1453       } // while (tasks)
1454
1455       visitedBitmapPtr.bitmap_free();
1456       workQueuePtr.queue_free();
1457       bQueryVectorPtr.vector_free();
1458       aQueryVectorPtr.vector_free();
1459       queryVectorPtr.vector_free();
1460       parentQueryVectorPtr.vector_free();
1461       queries = null;
1462     }
1463
1464
1465   /* =============================================================================
1466    * learner_run
1467    * -- Call adtree_make before this
1468    * =============================================================================
1469    */
1470   //Is not called anywhere now parallel code
1471   public void
1472     learner_run (int myId, int numThread, Learner learnerPtr)
1473     {
1474       {
1475         createTaskList(myId, numThread, learnerPtr);
1476       }
1477       {
1478         learnStructure(myId, numThread, learnerPtr);
1479       }
1480     }
1481
1482   /* =============================================================================
1483    * learner_score
1484    * -- Score entire network
1485    * =============================================================================
1486    */
1487   public float
1488     learner_score ()
1489     {
1490
1491       Vector_t queryVectorPtr = Vector_t.vector_alloc(1);
1492       Vector_t parentQueryVectorPtr = Vector_t.vector_alloc(1);
1493
1494       int numVar = adtreePtr.numVar;
1495       Query[] queries = new Query[numVar];
1496
1497       for (int v = 0; v < numVar; v++) {
1498         queries[v] = new Query();
1499         queries[v].index = v;
1500         queries[v].value = QUERY_VALUE_WILDCARD;
1501       }
1502
1503       int numTotalParent = 0;
1504       float logLikelihood = 0.0f;
1505
1506       for (int v = 0; v < numVar; v++) {
1507
1508         IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
1509         numTotalParent += parentIdListPtr.list_getSize();
1510
1511         populateQueryVectors(netPtr,
1512             v,
1513             queries,
1514             queryVectorPtr,
1515             parentQueryVectorPtr);
1516         float localLogLikelihood = computeLocalLogLikelihood(v,
1517             adtreePtr,
1518             netPtr,
1519             queries,
1520             queryVectorPtr,
1521             parentQueryVectorPtr);
1522         logLikelihood += localLogLikelihood;
1523       }
1524
1525       queryVectorPtr.vector_free();
1526       parentQueryVectorPtr.vector_free();
1527       queries = null;
1528
1529
1530       int numRecord = adtreePtr.numRecord;
1531       float penalty = (float)(-0.5f * (double)numTotalParent * Math.log((double)numRecord));
1532       float score = penalty + (float)numRecord * logLikelihood;
1533
1534       return score;
1535     }
1536 }
1537
1538 /* =============================================================================
1539  *
1540  * End of learner.java
1541  *
1542  * =============================================================================
1543  */