PLearn 0.1
RegressionTreeQueue.cc
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // RegressionTreeQueue.cc
00004 // Copyright (c) 1998-2002 Pascal Vincent
00005 // Copyright (C) 1999-2002 Yoshua Bengio and University of Montreal
00006 // Copyright (c) 2002 Jean-Sebastien Senecal, Xavier Saint-Mleux, Rejean Ducharme
00007 //
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions are met:
00010 // 
00011 //  1. Redistributions of source code must retain the above copyright
00012 //     notice, this list of conditions and the following disclaimer.
00013 // 
00014 //  2. Redistributions in binary form must reproduce the above copyright
00015 //     notice, this list of conditions and the following disclaimer in the
00016 //     documentation and/or other materials provided with the distribution.
00017 // 
00018 //  3. The name of the authors may not be used to endorse or promote
00019 //     products derived from this software without specific prior written
00020 //     permission.
00021 // 
00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 // 
00033 // This file is part of the PLearn library. For more information on the PLearn
00034 // library, go to the PLearn Web site at www.plearn.org
00035 
00036 
00037 /* ********************************************************************************    
00038  * $Id: RegressionTreeQueue.cc, v 1.0 2005/02/35 10:00:00 Bengio/Kegl/Godbout    *
00039  * This file is part of the PLearn library.                                     *
00040  ******************************************************************************** */
00041 
00042 #include "RegressionTreeQueue.h"
00043 #include "RegressionTreeNode.h"
00044 #include <plearn/base/tostring.h>
00045 
00046 namespace PLearn {
00047 using namespace std;
00048 
00049 PLEARN_IMPLEMENT_OBJECT(RegressionTreeQueue,
00050                         "Object to represent the priority queue of a regression tree.",
00051                         "The queue is used to keep all the nodes of the tree not yet expanded.\n"
00052                         "They are kept in a heap with the best possible split always on top.\n"
00053     );
00054 
00055 RegressionTreeQueue::RegressionTreeQueue()    
00056     : verbosity(0),
00057       maximum_number_of_nodes(400),
00058       next_available_node(0)
00059 {
00060     build();
00061 }
00062 RegressionTreeQueue::RegressionTreeQueue(int verbosity_,
00063                                          int maximum_number_of_nodes_)
00064     : verbosity(verbosity_),
00065       maximum_number_of_nodes(maximum_number_of_nodes_),
00066       next_available_node(0)
00067 {
00068     build();
00069 }
00070 RegressionTreeQueue::~RegressionTreeQueue()
00071 {
00072 }
00073 
00074 void RegressionTreeQueue::declareOptions(OptionList& ol)
00075 { 
00076     declareOption(ol, "verbosity", &RegressionTreeQueue::verbosity, OptionBase::buildoption,
00077                   "The desired level of verbosity\n");
00078     declareOption(ol, "maximum_number_of_nodes", &RegressionTreeQueue::maximum_number_of_nodes, OptionBase::buildoption,
00079                   "The maximum number of entries in the heap\n");
00080  
00081     declareOption(ol, "next_available_node", &RegressionTreeQueue::next_available_node, OptionBase::learntoption,
00082                   "The next available entry in the heap to add a node\n");
00083     declareOption(ol, "nodes", &RegressionTreeQueue::nodes, OptionBase::learntoption,
00084                   "The table of nodes kept with the best possible one to split on top\n");
00085     inherited::declareOptions(ol);
00086 }
00087 
00088 void RegressionTreeQueue::makeDeepCopyFromShallowCopy(CopiesMap& copies)
00089 {
00090     inherited::makeDeepCopyFromShallowCopy(copies);
00091     deepCopyField(verbosity, copies);
00092     deepCopyField(maximum_number_of_nodes, copies);
00093     deepCopyField(next_available_node, copies);
00094     deepCopyField(nodes, copies);
00095 }
00096 
00097 void RegressionTreeQueue::build()
00098 {
00099     inherited::build();
00100     build_();
00101 }
00102 
00103 void RegressionTreeQueue::build_()
00104 {
00105     nodes.resize(maximum_number_of_nodes);
00106 }
00107 
00108 void RegressionTreeQueue::addHeap(PP<RegressionTreeNode> new_node)
00109 {
00110     if (new_node->getErrorImprovment() < 0.0)
00111     {
00112         return;
00113     }
00114     if (next_available_node >= maximum_number_of_nodes){
00115         string s = "RegressionTreeQueue: maximum number of entries exceeded ("
00116             +tostring(maximum_number_of_nodes)+")";
00117         PLERROR(s.c_str());
00118     }
00119     nodes[next_available_node] = upHeap(new_node, next_available_node);
00120     next_available_node += 1;
00121 }
00122 
00123 PP<RegressionTreeNode> RegressionTreeQueue::popHeap()
00124 {
00125     PP<RegressionTreeNode> return_value;
00126     return_value = nodes[0];
00127     next_available_node -= 1;
00128     nodes[0] = downHeap(nodes[next_available_node], 0);
00129     return return_value;
00130 }
00131 
00132 PP<RegressionTreeNode> RegressionTreeQueue::upHeap(PP<RegressionTreeNode> new_node, int node_ind)
00133 {
00134     int parent_node;
00135     PP<RegressionTreeNode> saved_node;
00136     if (node_ind == 0) return new_node;
00137     parent_node = (node_ind - 1) / 2;
00138     if (compareNode(new_node, nodes[parent_node]) < 0)
00139     {
00140         saved_node = nodes[parent_node];
00141         nodes[parent_node] = upHeap(new_node, parent_node);
00142         return saved_node;      
00143     }
00144     return new_node;
00145 }
00146 
00147 PP<RegressionTreeNode> RegressionTreeQueue::downHeap(PP<RegressionTreeNode> new_node, int node_ind)
00148 {
00149     int left_child_node;
00150     int right_child_node;
00151     int smallest_child_node;
00152     PP<RegressionTreeNode> saved_node;
00153     left_child_node = 2 * node_ind + 1;
00154     if (left_child_node >= next_available_node) return new_node;
00155     right_child_node = 2 * node_ind + 2;
00156     smallest_child_node = left_child_node;
00157     if (right_child_node < next_available_node)
00158     {
00159         if (compareNode(nodes[left_child_node], nodes[right_child_node]) > 0)
00160         {
00161             smallest_child_node = right_child_node;
00162         }
00163     }
00164     if (compareNode(new_node, nodes[smallest_child_node]) > 0)    
00165     {
00166         saved_node = nodes[smallest_child_node];
00167         nodes[smallest_child_node] = downHeap(new_node, smallest_child_node);
00168         return saved_node;      
00169     }
00170     return new_node;
00171 }
00172 int RegressionTreeQueue::isEmpty()
00173 {
00174     return next_available_node;
00175 }
00176 
00177 int RegressionTreeQueue::compareNode(PP<RegressionTreeNode> node1, PP<RegressionTreeNode> node2)
00178 {
00179     if (node1->getErrorImprovment() > node2->getErrorImprovment()) return -1;
00180     if (node1->getErrorImprovment() < node2->getErrorImprovment()) return +1;
00181     if (node1->getSplitBalance() < node2->getSplitBalance()) return -1;
00182     return +1;
00183 }
00184 
00185 void RegressionTreeQueue::verbose(string the_msg, int the_level)
00186 {
00187     if (verbosity >= the_level)
00188         cout << the_msg << endl;
00189 }
00190 
00191 } // end of namespace PLearn
00192 
00193 
00194 /*
00195   Local Variables:
00196   mode:c++
00197   c-basic-offset:4
00198   c-file-style:"stroustrup"
00199   c-file-offsets:((innamespace . 0)(inline-open . 0))
00200   indent-tabs-mode:nil
00201   fill-column:79
00202   End:
00203 */
00204 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines