Alien-XGBoost
view release on metacpan or search on metacpan
xgboost/R-package/configure view on Meta::CPAN
program_suffix=NONE
program_transform_name=s,x,x,
silent=
site=
srcdir=
verbose=
x_includes=NONE
x_libraries=NONE
# Installation directory options.
# These are left unexpanded so users can "make install exec_prefix=/foo"
# and all the variables that are supposed to be based on exec_prefix
# by default will actually change.
# Use braces instead of parens because sh, perl, etc. also accept them.
# (The list follows the same order as the GNU Coding Standards.)
bindir='${exec_prefix}/bin'
sbindir='${exec_prefix}/sbin'
libexecdir='${exec_prefix}/libexec'
datarootdir='${prefix}/share'
datadir='${datarootdir}'
sysconfdir='${prefix}/etc'
xgboost/R-package/configure view on Meta::CPAN
fi
fi
else
{ $as_echo "$as_me:${as_lineno-$LINENO}: not updating unwritable cache $cache_file" >&5
$as_echo "$as_me: not updating unwritable cache $cache_file" >&6;}
fi
fi
rm -f confcache
test "x$prefix" = xNONE && prefix=$ac_default_prefix
# Let make expand exec_prefix.
test "x$exec_prefix" = xNONE && exec_prefix='${prefix}'
# Transform confdefs.h into DEFS.
# Protect against shell expansion while executing Makefile rules.
# Protect against Makefile macro expansion.
#
# If the first sed substitution is executed (which looks for macros that
# take arguments), then branch to the quote section. Otherwise,
# look for a macro that doesn't take arguments.
ac_script='
xgboost/R-package/configure view on Meta::CPAN
case $ac_mode in
:F)
#
# CONFIG_FILE
#
_ACEOF
cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1
# If the template does not know about datarootdir, expand it.
# FIXME: This hack should be removed a few years after 2.60.
ac_datarootdir_hack=; ac_datarootdir_seen=
ac_sed_dataroot='
/datarootdir/ {
p
q
}
/@datadir@/p
/@docdir@/p
/@infodir@/p
xgboost/cub/cub/util_type.cuh view on Meta::CPAN
T y;
T z;
T w;
typedef T BaseType;
typedef CubVector<T, 4> Type;
};
/**
* Macro for expanding partially-specialized built-in vector types
*/
#define CUB_DEFINE_VECTOR_TYPE(base_type,short_type) \
\
template<> struct CubVector<base_type, 1> : short_type##1 \
{ \
typedef base_type BaseType; \
typedef short_type##1 Type; \
__host__ __device__ __forceinline__ CubVector operator+(const CubVector &other) const { \
CubVector retval; \
retval.x = x + other.x; \
xgboost/dmlc-core/doc/Doxyfile view on Meta::CPAN
#---------------------------------------------------------------------------
# Configuration options related to the preprocessor
#---------------------------------------------------------------------------
# If the ENABLE_PREPROCESSING tag is set to YES (the default) Doxygen will
# evaluate all C-preprocessor directives found in the sources and include
# files.
ENABLE_PREPROCESSING = NO
# If the MACRO_EXPANSION tag is set to YES Doxygen will expand all macro
# names in the source code. If set to NO (the default) only conditional
# compilation will be performed. Macro expansion can be done in a controlled
# way by setting EXPAND_ONLY_PREDEF to YES.
MACRO_EXPANSION = NO
# If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES
# then the macro expansion is limited to the macros specified with the
# PREDEFINED and EXPAND_AS_DEFINED tags.
xgboost/dmlc-core/doc/Doxyfile view on Meta::CPAN
# directories. If left blank, the patterns specified with FILE_PATTERNS will
# be used.
INCLUDE_FILE_PATTERNS =
# The PREDEFINED tag can be used to specify one or more macro names that
# are defined before the preprocessor is started (similar to the -D option of
# gcc). The argument of the tag is a list of macros of the form: name
# or name=definition (no spaces). If the definition and the = are
# omitted =1 is assumed. To prevent a macro definition from being
# undefined via #undef or recursively expanded use the := operator
# instead of the = operator.
PREDEFINED =
# If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then
# this tag can be used to specify a list of macro names that should be expanded.
# The macro definition that is found in the sources will be used.
# Use the PREDEFINED tag if you want to use a different macro definition that
# overrules the definition found in the source code.
EXPAND_AS_DEFINED =
# If the SKIP_FUNCTION_MACROS tag is set to YES (the default) then
# doxygen's preprocessor will remove all references to function-like macros
# that are alone on a line, have an all uppercase name, and do not end with a
# semicolon, because these will confuse the parser if not removed.
xgboost/dmlc-core/doc/conf.py view on Meta::CPAN
#
# All configuration values have a default; values that are commented out
# serve to show the default.
import sys
import os, subprocess
import shlex
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here. If the directory is relative to the
# documentation root, use os.path.abspath to make it absolute, like shown here.
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
sys.path.insert(0, curr_path)
from sphinx_util import MarkdownParser, AutoStructify
# -- General configuration ------------------------------------------------
# General information about the project.
project = u'dmlc-core'
copyright = u'2015, dmlc-core developers'
author = u'dmlc-core developers'
github_doc_root = 'https://github.com/dmlc-core/dmlc-core/tree/master/doc/'
xgboost/dmlc-core/doc/parameter.md view on Meta::CPAN
MyParam param;
std::vector<std::pair<std::string, std::string> > param_data = {
{"num_hidden", "100"},
};
param.Init(param_data);
return 0;
}
```
The secrete lies in the function ```DMLC_DECLARE_PARAMETER(MyParam)```, this is an macro defined in the parameter module.
If we expand the micro, the code roughly becomes the following code.
```c++
struct Parameter<MyParam> {
template<typename ValueType>
inline FieldEntry<ValueType>&
DECLARE(ParamManagerSingleton<MyParam> *manager,
const std::string& key,
ValueType& ref){
// offset gives a generic way to access the address of the field
// from beginning of the structure.
xgboost/dmlc-core/src/io/input_split_base.cc view on Meta::CPAN
while (str.length() != 0 && str[str.length() - 1] == ch) {
str.resize(str.length() - 1);
}
return str;
}
void InputSplitBase::InitInputFileInfo(const std::string& uri) {
// split by :
const char dlm = ';';
std::vector<std::string> file_list = Split(uri, dlm);
std::vector<URI> expanded_list;
// expand by match regex pattern.
for (size_t i = 0; i < file_list.size(); ++i) {
URI path(file_list[i].c_str());
size_t pos = path.name.rfind('/');
if (pos == std::string::npos || pos + 1 == path.name.length()) {
expanded_list.push_back(path);
} else {
URI dir = path;
dir.name = path.name.substr(0, pos);
std::vector<FileInfo> dfiles;
filesys_->ListDirectory(dir, &dfiles);
bool exact_match = false;
for (size_t i = 0; i < dfiles.size(); ++i) {
if (StripEnd(dfiles[i].path.name, '/') == StripEnd(path.name, '/')) {
expanded_list.push_back(dfiles[i].path);
exact_match = true;
break;
}
}
#if DMLC_USE_REGEX
if (!exact_match) {
std::string spattern = path.name;
try {
std::regex pattern(spattern);
for (size_t i = 0; i < dfiles.size(); ++i) {
if (dfiles[i].type != kFile || dfiles[i].size == 0) continue;
std::string stripped = StripEnd(dfiles[i].path.name, '/');
std::smatch base_match;
if (std::regex_match(stripped, base_match, pattern)) {
for (size_t j = 0; j < base_match.size(); ++j) {
if (base_match[j].str() == stripped) {
expanded_list.push_back(dfiles[i].path); break;
}
}
}
}
} catch (std::regex_error& e) {
LOG(FATAL) << e.what() << " bad regex " << spattern
<< "This could due to compiler version, g++-4.9 is needed";
}
}
#endif // DMLC_USE_REGEX
}
}
for (size_t i = 0; i < expanded_list.size(); ++i) {
const URI& path = expanded_list[i];
FileInfo info = filesys_->GetPathInfo(path);
if (info.type == kDirectory) {
std::vector<FileInfo> dfiles;
filesys_->ListDirectory(info.path, &dfiles);
for (size_t i = 0; i < dfiles.size(); ++i) {
if (dfiles[i].size != 0 && dfiles[i].type == kFile) {
files_.push_back(dfiles[i]);
}
}
} else {
xgboost/dmlc-core/tracker/dmlc-submit view on Meta::CPAN
#!/usr/bin/env python
import sys
import os
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
sys.path.insert(0, curr_path)
from dmlc_tracker import submit
submit.main()
xgboost/dmlc-core/tracker/dmlc_tracker/yarn.py view on Meta::CPAN
if args.jobname is None:
if args.num_servers == 0:
prefix = ('DMLC[nworker=%d]:' % args.num_workers)
else:
prefix = ('DMLC[nworker=%d,nsever=%d]:' % (args.num_workers, args.num_servers))
args.jobname = prefix + args.command[0].split('/')[-1]
# Determine path for Yarn helpers
YARN_JAR_PATH = os.path.join(args.yarn_app_dir, 'dmlc-yarn.jar')
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
YARN_BOOT_PY = os.path.join(curr_path, 'launcher.py')
if not os.path.exists(YARN_JAR_PATH):
warnings.warn("cannot find \"%s\", I will try to run build" % YARN_JAR_PATH)
cmd = 'cd %s;./build.%s' % \
(os.path.join(os.path.dirname(__file__), os.pardir, 'yarn'),
'bat' if is_windows else 'sh')
print(cmd)
subprocess.check_call(cmd, shell=True, env=os.environ)
assert os.path.exists(YARN_JAR_PATH), "failed to build dmlc-yarn.jar, try it manually"
xgboost/dmlc-core/tracker/dmlc_tracker/yarn.py view on Meta::CPAN
thread = Thread(target=run, args=())
thread.setDaemon(True)
thread.start()
return thread
def submit(args):
submit_thread = []
def yarn_submit_pass(nworker, nserver, pass_env):
submit_thread.append(yarn_submit(args, nworker, nserver, pass_env))
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
YARN_BOOT_PY = os.path.join(curr_path, 'launcher.py')
tracker.submit(args.num_workers, args.num_servers,
fun_submit=yarn_submit_pass,
pscmd=(' '.join([YARN_BOOT_PY] + args.command)))
for thread in submit_thread:
thread.join()
xgboost/doc/Doxyfile view on Meta::CPAN
# If the HTML_DYNAMIC_SECTIONS tag is set to YES then the generated HTML
# documentation will contain sections that can be hidden and shown after the
# page has loaded.
# The default value is: NO.
# This tag requires that the tag GENERATE_HTML is set to YES.
HTML_DYNAMIC_SECTIONS = NO
# With HTML_INDEX_NUM_ENTRIES one can control the preferred number of entries
# shown in the various tree structured indices initially; the user can expand
# and collapse entries dynamically later on. Doxygen will expand the tree to
# such a level that at most the specified number of entries are visible (unless
# a fully collapsed tree already exceeds this amount). So setting the number of
# entries 1 will produce a full collapsed tree by default. 0 is a special value
# representing an infinite number of entries and will result in a full expanded
# tree by default.
# Minimum value: 0, maximum value: 9999, default value: 100.
# This tag requires that the tag GENERATE_HTML is set to YES.
#HTML_INDEX_NUM_ENTRIES = 100
# If the GENERATE_DOCSET tag is set to YES, additional index files will be
# generated that can be used as input for Apple's Xcode 3 integrated development
# environment (see: http://developer.apple.com/tools/xcode/), introduced with
# OSX 10.5 (Leopard). To create a documentation set, doxygen will generate a
xgboost/doc/Doxyfile view on Meta::CPAN
#---------------------------------------------------------------------------
# Configuration options related to the preprocessor
#---------------------------------------------------------------------------
# If the ENABLE_PREPROCESSING tag is set to YES doxygen will evaluate all
# C-preprocessor directives found in the sources and include files.
# The default value is: YES.
ENABLE_PREPROCESSING = YES
# If the MACRO_EXPANSION tag is set to YES doxygen will expand all macro names
# in the source code. If set to NO only conditional compilation will be
# performed. Macro expansion can be done in a controlled way by setting
# EXPAND_ONLY_PREDEF to YES.
# The default value is: NO.
# This tag requires that the tag ENABLE_PREPROCESSING is set to YES.
MACRO_EXPANSION = NO
# If the EXPAND_ONLY_PREDEF and MACRO_EXPANSION tags are both set to YES then
# the macro expansion is limited to the macros specified with the PREDEFINED and
xgboost/doc/Doxyfile view on Meta::CPAN
# used.
# This tag requires that the tag ENABLE_PREPROCESSING is set to YES.
INCLUDE_FILE_PATTERNS =
# The PREDEFINED tag can be used to specify one or more macro names that are
# defined before the preprocessor is started (similar to the -D option of e.g.
# gcc). The argument of the tag is a list of macros of the form: name or
# name=definition (no spaces). If the definition and the "=" are omitted, "=1"
# is assumed. To prevent a macro definition from being undefined via #undef or
# recursively expanded use the := operator instead of the = operator.
# This tag requires that the tag ENABLE_PREPROCESSING is set to YES.
PREDEFINED = DMLC_USE_CXX11
# If the MACRO_EXPANSION and EXPAND_ONLY_PREDEF tags are set to YES then this
# tag can be used to specify a list of macro names that should be expanded. The
# macro definition that is found in the sources will be used. Use the PREDEFINED
# tag if you want to use a different macro definition that overrules the
# definition found in the source code.
# This tag requires that the tag ENABLE_PREPROCESSING is set to YES.
EXPAND_AS_DEFINED =
# If the SKIP_FUNCTION_MACROS tag is set to YES then doxygen's preprocessor will
# remove all references to function-like macros that are alone on a line, have
# an all uppercase name, and do not end with a semicolon. Such function macros
xgboost/doc/_static/xgboost-theme/navbar.html view on Meta::CPAN
<div class="navbar navbar-default navbar-fixed-top">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#navbar" aria-expanded="false" aria-controls="navbar">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
</div>
<div id="navbar" class="navbar-collapse collapse">
<ul id="navbar" class="navbar navbar-left">
<li> <a href="{{url_root}}">XGBoost</a> </li>
{% for name in ['Get Started', 'Tutorials', 'How To'] %}
<li> <a href="{{url_root}}{{name.lower()|replace(" ", "_")}}/index.html">{{name}}</a> </li>
{% endfor %}
{% for name in ['Packages'] %}
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="true">{{name}} <span class="caret"></span></a>
<ul class="dropdown-menu">
<li><a href="{{url_root}}python/index.html">Python</a></li>
<li><a href="{{url_root}}R-package/index.html">R</a></li>
<li><a href="{{url_root}}jvm/index.html">JVM</a></li>
<li><a href="{{url_root}}julia/index.html">Julia</a></li>
<li><a href="{{url_root}}cli/index.html">CLI</a></li>
</ul>
</li>
{% endfor %}
<li> <a href="{{url_root}}/parameter.html"> Knobs </a> </li>
xgboost/doc/conf.py view on Meta::CPAN
#
# All configuration values have a default; values that are commented out
# serve to show the default.
import sys
import os, subprocess
import shlex
import urllib
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here. If the directory is relative to the
# documentation root, use os.path.abspath to make it absolute, like shown here.
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
libpath = os.path.join(curr_path, '../python-package/')
sys.path.insert(0, libpath)
sys.path.insert(0, curr_path)
from sphinx_util import MarkdownParser, AutoStructify
# -- mock out modules
import mock
MOCK_MODULES = ['numpy', 'scipy', 'scipy.sparse', 'sklearn', 'matplotlib', 'pandas', 'graphviz']
for mod_name in MOCK_MODULES:
xgboost/python-package/xgboost/libpath.py view on Meta::CPAN
def find_lib_path():
"""Find the path to xgboost dynamic library files.
Returns
-------
lib_path: list(string)
List of all found library path to xgboost
"""
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
# make pythonpack hack: copy this directory one level upper for setup.py
dll_path = [curr_path, os.path.join(curr_path, '../../lib/'),
os.path.join(curr_path, './lib/'),
os.path.join(sys.prefix, 'xgboost')]
if sys.platform == 'win32':
if platform.architecture()[0] == '64bit':
dll_path.append(os.path.join(curr_path, '../../windows/x64/Release/'))
# hack for pip installation when copy all parent source directory here
dll_path.append(os.path.join(curr_path, './windows/x64/Release/'))
else:
xgboost/rabit/doc/conf.py view on Meta::CPAN
# autogenerated file.
#
# All configuration values have a default; values that are commented out
# serve to show the default.
import sys
import os, subprocess
import shlex
# If extensions (or modules to document with autodoc) are in another directory,
# add these directories to sys.path here. If the directory is relative to the
# documentation root, use os.path.abspath to make it absolute, like shown here.
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
libpath = os.path.join(curr_path, '../wrapper/')
sys.path.insert(0, os.path.join(curr_path, '../wrapper/'))
sys.path.insert(0, curr_path)
from sphinx_util import MarkdownParser, AutoStructify
# -- General configuration ------------------------------------------------
# General information about the project.
project = u'rabit'
copyright = u'2015, rabit developers'
xgboost/rabit/python/rabit.py view on Meta::CPAN
_LIB = None
def _find_lib_path(dll_name):
"""Find the rabit dynamic library files.
Returns
-------
lib_path: list(string)
List of all found library path to rabit
"""
curr_path = os.path.dirname(os.path.abspath(os.path.expanduser(__file__)))
# make pythonpack hack: copy this directory one level upper for setup.py
dll_path = [curr_path,
os.path.join(curr_path, '../lib/'),
os.path.join(curr_path, './lib/')]
if os.name == 'nt':
dll_path = [os.path.join(p, dll_name) for p in dll_path]
else:
dll_path = [os.path.join(p, dll_name) for p in dll_path]
lib_path = [p for p in dll_path if os.path.exists(p) and os.path.isfile(p)]
#From github issues, most of installation errors come from machines w/o compilers
xgboost/src/tree/updater_basemaker-inl.h view on Meta::CPAN
if (param.subsample < 1.0f) {
std::bernoulli_distribution coin_flip(param.subsample);
auto& rnd = common::GlobalRandom();
for (size_t i = 0; i < position.size(); ++i) {
if (gpair[i].hess < 0.0f) continue;
if (!coin_flip(rnd)) position[i] = ~position[i];
}
}
}
{
// expand query
qexpand.reserve(256); qexpand.clear();
for (int i = 0; i < tree.param.num_roots; ++i) {
qexpand.push_back(i);
}
this->UpdateNode2WorkIndex(tree);
}
}
/*! \brief update queue expand add in new leaves */
inline void UpdateQueueExpand(const RegTree &tree) {
std::vector<int> newnodes;
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
if (!tree[nid].is_leaf()) {
newnodes.push_back(tree[nid].cleft());
newnodes.push_back(tree[nid].cright());
}
}
// use new nodes for qexpand
qexpand = newnodes;
this->UpdateNode2WorkIndex(tree);
}
// return decoded position
inline int DecodePosition(bst_uint ridx) const {
const int pid = position[ridx];
return pid < 0 ? ~pid : pid;
}
// encode the encoded position value for ridx
inline void SetEncodePosition(bst_uint ridx, int nid) {
if (position[ridx] < 0) {
xgboost/src/tree/updater_basemaker-inl.h view on Meta::CPAN
std::vector< std::vector<TStats> > *p_thread_temp,
std::vector<TStats> *p_node_stats) {
std::vector< std::vector<TStats> > &thread_temp = *p_thread_temp;
const MetaInfo &info = fmat.info();
thread_temp.resize(omp_get_max_threads());
p_node_stats->resize(tree.param.num_nodes);
#pragma omp parallel
{
const int tid = omp_get_thread_num();
thread_temp[tid].resize(tree.param.num_nodes, TStats(param));
for (size_t i = 0; i < qexpand.size(); ++i) {
const unsigned nid = qexpand[i];
thread_temp[tid][nid].Clear();
}
}
const RowSet &rowset = fmat.buffered_rowset();
// setup position
const bst_omp_uint ndata = static_cast<bst_omp_uint>(rowset.size());
#pragma omp parallel for schedule(static)
for (bst_omp_uint i = 0; i < ndata; ++i) {
const bst_uint ridx = rowset[i];
const int nid = position[ridx];
const int tid = omp_get_thread_num();
if (nid >= 0) {
thread_temp[tid][nid].Add(gpair, info, ridx);
}
}
// sum the per thread statistics together
for (size_t j = 0; j < qexpand.size(); ++j) {
const int nid = qexpand[j];
TStats &s = (*p_node_stats)[nid];
s.Clear();
for (size_t tid = 0; tid < thread_temp.size(); ++tid) {
s.Add(thread_temp[tid][nid]);
}
}
}
/*! \brief common helper data structure to build sketch */
struct SketchEntry {
/*! \brief total sum of amount to be met */
xgboost/src/tree/updater_basemaker-inl.h view on Meta::CPAN
Entry(static_cast<bst_float>(rmin),
static_cast<bst_float>(rmax),
static_cast<bst_float>(wmin), last_fvalue);
++sketch->temp.size;
}
sketch->PushTemp();
}
};
/*! \brief training parameter of tree grower */
TrainParam param;
/*! \brief queue of nodes to be expanded */
std::vector<int> qexpand;
/*!
* \brief map active node to is working index offset in qexpand,
* can be -1, which means the node is node actively expanding
*/
std::vector<int> node2workindex;
/*!
* \brief position of each instance in the tree
* can be negative, which means this position is no longer expanding
* see also Decode/EncodePosition
*/
std::vector<int> position;
private:
inline void UpdateNode2WorkIndex(const RegTree &tree) {
// update the node2workindex
std::fill(node2workindex.begin(), node2workindex.end(), -1);
node2workindex.resize(tree.param.num_nodes);
for (size_t i = 0; i < qexpand.size(); ++i) {
node2workindex[qexpand[i]] = static_cast<int>(i);
}
}
};
} // namespace tree
} // namespace xgboost
#endif // XGBOOST_TREE_UPDATER_BASEMAKER_INL_H_
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
// actual builder that runs the algorithm
struct Builder {
public:
// constructor
explicit Builder(const TrainParam& param) : param(param), nthread(omp_get_max_threads()) {}
// update one tree, growing
virtual void Update(const std::vector<bst_gpair>& gpair,
DMatrix* p_fmat,
RegTree* p_tree) {
this->InitData(gpair, *p_fmat, *p_tree);
this->InitNewNode(qexpand_, gpair, *p_fmat, *p_tree);
for (int depth = 0; depth < param.max_depth; ++depth) {
this->FindSplit(depth, qexpand_, gpair, p_fmat, p_tree);
this->ResetPosition(qexpand_, p_fmat, *p_tree);
this->UpdateQueueExpand(*p_tree, &qexpand_);
this->InitNewNode(qexpand_, gpair, *p_fmat, *p_tree);
// if nothing left to be expand, break
if (qexpand_.size() == 0) break;
}
// set all the rest expanding nodes to leaf
for (size_t i = 0; i < qexpand_.size(); ++i) {
const int nid = qexpand_[i];
(*p_tree)[nid].set_leaf(snode[nid].weight * param.learning_rate);
}
// remember auxiliary statistics in the tree node
for (int nid = 0; nid < p_tree->param.num_nodes; ++nid) {
p_tree->stat(nid).loss_chg = snode[nid].best.loss_chg;
p_tree->stat(nid).base_weight = snode[nid].weight;
p_tree->stat(nid).sum_hess = static_cast<float>(snode[nid].stats.sum_hess);
snode[nid].stats.SetLeafVec(param, p_tree->leafvec(nid));
}
}
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
// setup temp space for each thread
// reserve a small space
stemp.clear();
stemp.resize(this->nthread, std::vector<ThreadEntry>());
for (size_t i = 0; i < stemp.size(); ++i) {
stemp[i].clear(); stemp[i].reserve(256);
}
snode.reserve(256);
}
{
// expand query
qexpand_.reserve(256); qexpand_.clear();
for (int i = 0; i < tree.param.num_roots; ++i) {
qexpand_.push_back(i);
}
}
}
/*!
* \brief initialize the base_weight, root_gain,
* and NodeEntry for all the new nodes in qexpand
*/
inline void InitNewNode(const std::vector<int>& qexpand,
const std::vector<bst_gpair>& gpair,
const DMatrix& fmat,
const RegTree& tree) {
{
// setup statistics space for each tree node
for (size_t i = 0; i < stemp.size(); ++i) {
stemp[i].resize(tree.param.num_nodes, ThreadEntry(param));
}
snode.resize(tree.param.num_nodes, NodeEntry(param));
constraints_.resize(tree.param.num_nodes);
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
// setup position
const bst_omp_uint ndata = static_cast<bst_omp_uint>(rowset.size());
#pragma omp parallel for schedule(static)
for (bst_omp_uint i = 0; i < ndata; ++i) {
const bst_uint ridx = rowset[i];
const int tid = omp_get_thread_num();
if (position[ridx] < 0) continue;
stemp[tid][position[ridx]].stats.Add(gpair, info, ridx);
}
// sum the per thread statistics together
for (size_t j = 0; j < qexpand.size(); ++j) {
const int nid = qexpand[j];
TStats stats(param);
for (size_t tid = 0; tid < stemp.size(); ++tid) {
stats.Add(stemp[tid][nid].stats);
}
// update node statistics
snode[nid].stats = stats;
}
// setup constraints before calculating the weight
for (size_t j = 0; j < qexpand.size(); ++j) {
const int nid = qexpand[j];
if (tree[nid].is_root()) continue;
const int pid = tree[nid].parent();
constraints_[pid].SetChild(param, tree[pid].split_index(),
snode[tree[pid].cleft()].stats,
snode[tree[pid].cright()].stats,
&constraints_[tree[pid].cleft()],
&constraints_[tree[pid].cright()]);
}
// calculating the weights
for (size_t j = 0; j < qexpand.size(); ++j) {
const int nid = qexpand[j];
snode[nid].root_gain = static_cast<float>(
constraints_[nid].CalcGain(param, snode[nid].stats));
snode[nid].weight = static_cast<float>(
constraints_[nid].CalcWeight(param, snode[nid].stats));
}
}
/*! \brief update queue expand add in new leaves */
inline void UpdateQueueExpand(const RegTree& tree, std::vector<int>* p_qexpand) {
std::vector<int> &qexpand = *p_qexpand;
std::vector<int> newnodes;
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
if (!tree[ nid ].is_leaf()) {
newnodes.push_back(tree[nid].cleft());
newnodes.push_back(tree[nid].cright());
}
}
// use new nodes for qexpand
qexpand = newnodes;
}
// parallel find the best split of current fid
// this function does not support nested functions
inline void ParallelFindSplit(const ColBatch::Inst &col,
bst_uint fid,
const DMatrix &fmat,
const std::vector<bst_gpair> &gpair) {
// TODO(tqchen): double check stats order.
const MetaInfo& info = fmat.info();
const bool ind = col.length != 0 && col.data[0].fvalue == col.data[col.length - 1].fvalue;
bool need_forward = param.need_forward_search(fmat.GetColDensity(fid), ind);
bool need_backward = param.need_backward_search(fmat.GetColDensity(fid), ind);
const std::vector<int> &qexpand = qexpand_;
#pragma omp parallel
{
const int tid = omp_get_thread_num();
std::vector<ThreadEntry> &temp = stemp[tid];
// cleanup temp statistics
for (size_t j = 0; j < qexpand.size(); ++j) {
temp[qexpand[j]].stats.Clear();
}
bst_uint step = (col.length + this->nthread - 1) / this->nthread;
bst_uint end = std::min(col.length, step * (tid + 1));
for (bst_uint i = tid * step; i < end; ++i) {
const bst_uint ridx = col[i].index;
const int nid = position[ridx];
if (nid < 0) continue;
const bst_float fvalue = col[i].fvalue;
if (temp[nid].stats.Empty()) {
temp[nid].first_fvalue = fvalue;
}
temp[nid].stats.Add(gpair, info, ridx);
temp[nid].last_fvalue = fvalue;
}
}
// start collecting the partial sum statistics
bst_omp_uint nnode = static_cast<bst_omp_uint>(qexpand.size());
#pragma omp parallel for schedule(static)
for (bst_omp_uint j = 0; j < nnode; ++j) {
const int nid = qexpand[j];
TStats sum(param), tmp(param), c(param);
for (int tid = 0; tid < this->nthread; ++tid) {
tmp = stemp[tid][nid].stats;
stemp[tid][nid].stats = sum;
sum.Add(tmp);
if (tid != 0) {
std::swap(stemp[tid - 1][nid].last_fvalue, stemp[tid][nid].first_fvalue);
}
}
for (int tid = 0; tid < this->nthread; ++tid) {
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
e.last_fvalue = fvalue;
}
}
// same as EnumerateSplit, with cacheline prefetch optimization
inline void EnumerateSplitCacheOpt(const ColBatch::Entry *begin,
const ColBatch::Entry *end,
int d_step,
bst_uint fid,
const std::vector<bst_gpair> &gpair,
std::vector<ThreadEntry> &temp) { // NOLINT(*)
const std::vector<int> &qexpand = qexpand_;
// clear all the temp statistics
for (size_t j = 0; j < qexpand.size(); ++j) {
temp[qexpand[j]].stats.Clear();
}
// left statistics
TStats c(param);
// local cache buffer for position and gradient pair
const int kBuffer = 32;
int buf_position[kBuffer];
bst_gpair buf_gpair[kBuffer];
// aligned ending position
const ColBatch::Entry *align_end;
if (d_step > 0) {
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
buf_gpair[i] = gpair[it->index];
}
for (it = align_end, i = 0; it != end; ++i, it += d_step) {
const int nid = buf_position[i];
if (nid < 0) continue;
this->UpdateEnumeration(nid, buf_gpair[i],
it->fvalue, d_step,
fid, c, temp);
}
// finish updating all statistics, check if it is possible to include all sum statistics
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
ThreadEntry &e = temp[nid];
c.SetSubstract(snode[nid].stats, e.stats);
if (e.stats.sum_hess >= param.min_child_weight &&
c.sum_hess >= param.min_child_weight) {
bst_float loss_chg;
if (d_step == -1) {
loss_chg = static_cast<bst_float>(
constraints_[nid].CalcSplitGain(param, fid, c, e.stats) - snode[nid].root_gain);
} else {
loss_chg = static_cast<bst_float>(
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
int d_step,
bst_uint fid,
const std::vector<bst_gpair> &gpair,
const MetaInfo &info,
std::vector<ThreadEntry> &temp) { // NOLINT(*)
// use cacheline aware optimization
if (TStats::kSimpleStats != 0 && param.cache_opt != 0) {
EnumerateSplitCacheOpt(begin, end, d_step, fid, gpair, temp);
return;
}
const std::vector<int> &qexpand = qexpand_;
// clear all the temp statistics
for (size_t j = 0; j < qexpand.size(); ++j) {
temp[qexpand[j]].stats.Clear();
}
// left statistics
TStats c(param);
for (const ColBatch::Entry *it = begin; it != end; it += d_step) {
const bst_uint ridx = it->index;
const int nid = position[ridx];
if (nid < 0) continue;
// start working
const bst_float fvalue = it->fvalue;
// get the statistics of nid
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
}
e.best.Update(loss_chg, fid, (fvalue + e.last_fvalue) * 0.5f, d_step == -1);
}
}
// update the statistics
e.stats.Add(gpair, info, ridx);
e.last_fvalue = fvalue;
}
}
// finish updating all statistics, check if it is possible to include all sum statistics
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
ThreadEntry &e = temp[nid];
c.SetSubstract(snode[nid].stats, e.stats);
if (e.stats.sum_hess >= param.min_child_weight && c.sum_hess >= param.min_child_weight) {
bst_float loss_chg;
if (d_step == -1) {
loss_chg = static_cast<bst_float>(
constraints_[nid].CalcSplitGain(param, fid, c, e.stats) - snode[nid].root_gain);
} else {
loss_chg = static_cast<bst_float>(
constraints_[nid].CalcSplitGain(param, fid, e.stats, c) - snode[nid].root_gain);
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
}
} else {
for (bst_omp_uint i = 0; i < nsize; ++i) {
this->ParallelFindSplit(batch[i], batch.col_index[i],
fmat, gpair);
}
}
}
// find splits at current level, do split per level
inline void FindSplit(int depth,
const std::vector<int> &qexpand,
const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
RegTree *p_tree) {
std::vector<bst_uint> feat_set = feat_index;
if (param.colsample_bylevel != 1.0f) {
std::shuffle(feat_set.begin(), feat_set.end(), common::GlobalRandom());
unsigned n = std::max(static_cast<unsigned>(1),
static_cast<unsigned>(param.colsample_bylevel * feat_index.size()));
CHECK_GT(param.colsample_bylevel, 0U)
<< "colsample_bylevel cannot be zero.";
feat_set.resize(n);
}
dmlc::DataIter<ColBatch>* iter = p_fmat->ColIterator(feat_set);
while (iter->Next()) {
this->UpdateSolution(iter->Value(), gpair, *p_fmat);
}
// after this each thread's stemp will get the best candidates, aggregate results
this->SyncBestSolution(qexpand);
// get the best result, we can synchronize the solution
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
NodeEntry &e = snode[nid];
// now we know the solution in snode[nid], set split
if (e.best.loss_chg > rt_eps) {
p_tree->AddChilds(nid);
(*p_tree)[nid].set_split(e.best.split_index(), e.best.split_value, e.best.default_left());
// mark right child as 0, to indicate fresh leaf
(*p_tree)[(*p_tree)[nid].cleft()].set_leaf(0.0f, 0);
(*p_tree)[(*p_tree)[nid].cright()].set_leaf(0.0f, 0);
} else {
(*p_tree)[nid].set_leaf(e.weight * param.learning_rate);
}
}
}
// reset position of each data points after split is created in the tree
inline void ResetPosition(const std::vector<int> &qexpand,
DMatrix* p_fmat,
const RegTree& tree) {
// set the positions in the nondefault
this->SetNonDefaultPosition(qexpand, p_fmat, tree);
// set rest of instances to default position
const RowSet &rowset = p_fmat->buffered_rowset();
// set default direct nodes to default
// for leaf nodes that are not fresh, mark then to ~nid,
// so that they are ignored in future statistics collection
const bst_omp_uint ndata = static_cast<bst_omp_uint>(rowset.size());
#pragma omp parallel for schedule(static)
for (bst_omp_uint i = 0; i < ndata; ++i) {
const bst_uint ridx = rowset[i];
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
if (tree[nid].default_left()) {
this->SetEncodePosition(ridx, tree[nid].cleft());
} else {
this->SetEncodePosition(ridx, tree[nid].cright());
}
}
}
}
// customization part
// synchronize the best solution of each node
virtual void SyncBestSolution(const std::vector<int> &qexpand) {
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
NodeEntry &e = snode[nid];
for (int tid = 0; tid < this->nthread; ++tid) {
e.best.Update(stemp[tid][nid].best);
}
}
}
virtual void SetNonDefaultPosition(const std::vector<int> &qexpand,
DMatrix *p_fmat,
const RegTree &tree) {
// step 1, classify the non-default data into right places
std::vector<unsigned> fsplits;
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
if (!tree[nid].is_leaf()) {
fsplits.push_back(tree[nid].split_index());
}
}
std::sort(fsplits.begin(), fsplits.end());
fsplits.resize(std::unique(fsplits.begin(), fsplits.end()) - fsplits.begin());
dmlc::DataIter<ColBatch> *iter = p_fmat->ColIterator(fsplits);
while (iter->Next()) {
const ColBatch &batch = iter->Value();
for (size_t i = 0; i < batch.size; ++i) {
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
// number of omp thread used during training
const int nthread;
// Per feature: shuffle index of each feature index
std::vector<bst_uint> feat_index;
// Instance Data: current node position in the tree of each instance
std::vector<int> position;
// PerThread x PerTreeNode: statistics for per thread construction
std::vector< std::vector<ThreadEntry> > stemp;
/*! \brief TreeNode Data: statistics for each constructed node */
std::vector<NodeEntry> snode;
/*! \brief queue of nodes to be expanded */
std::vector<int> qexpand_;
// constraint value
std::vector<TConstraint> constraints_;
};
};
// distributed column maker
template<typename TStats, typename TConstraint>
class DistColMaker : public ColMaker<TStats, TConstraint> {
public:
DistColMaker() : builder(param) {
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
CHECK_GE(nid, 0);
}
this->position[ridx] = nid;
}
}
inline const int* GetLeafPosition() const {
return dmlc::BeginPtr(this->position);
}
protected:
void SetNonDefaultPosition(const std::vector<int> &qexpand,
DMatrix *p_fmat,
const RegTree &tree) override {
// step 2, classify the non-default data into right places
std::vector<unsigned> fsplits;
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
if (!tree[nid].is_leaf()) {
fsplits.push_back(tree[nid].split_index());
}
}
// get the candidate split index
std::sort(fsplits.begin(), fsplits.end());
fsplits.resize(std::unique(fsplits.begin(), fsplits.end()) - fsplits.begin());
while (fsplits.size() != 0 && fsplits.back() >= p_fmat->info().num_col) {
fsplits.pop_back();
}
xgboost/src/tree/updater_colmaker.cc view on Meta::CPAN
CHECK(!tree[nid].is_leaf()) << "inconsistent reduce information";
if (tree[nid].default_left()) {
this->SetEncodePosition(ridx, tree[nid].cright());
} else {
this->SetEncodePosition(ridx, tree[nid].cleft());
}
}
}
}
// synchronize the best solution of each node
void SyncBestSolution(const std::vector<int> &qexpand) override {
std::vector<SplitEntry> vec;
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
for (int tid = 0; tid < this->nthread; ++tid) {
this->snode[nid].best.Update(this->stemp[tid][nid].best);
}
vec.push_back(this->snode[nid].best);
}
// TODO(tqchen) lazy version
// communicate best solution
reducer.Allreduce(dmlc::BeginPtr(vec), vec.size());
// assign solution back
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
this->snode[nid].best = vec[i];
}
}
private:
common::BitMap bitmap;
std::vector<int> boolmap;
rabit::Reducer<SplitEntry, SplitEntry::Reduce> reducer;
};
// we directly introduce pruner here
xgboost/src/tree/updater_fast_hist.cc view on Meta::CPAN
BuildHist(gpair, row_set_collection_[nid], gmat, gmatb, feat_set, hist_[nid]);
time_build_hist += dmlc::GetTime() - tstart;
tstart = dmlc::GetTime();
this->InitNewNode(nid, gmat, gpair, *p_fmat, *p_tree);
time_init_new_node += dmlc::GetTime() - tstart;
tstart = dmlc::GetTime();
this->EvaluateSplit(nid, gmat, hist_, *p_fmat, *p_tree, feat_set);
time_evaluate_split += dmlc::GetTime() - tstart;
qexpand_->push(ExpandEntry(nid, p_tree->GetDepth(nid),
snode[nid].best.loss_chg,
timestamp++));
++num_leaves;
}
while (!qexpand_->empty()) {
const ExpandEntry candidate = qexpand_->top();
const int nid = candidate.nid;
qexpand_->pop();
if (candidate.loss_chg <= rt_eps
|| (param.max_depth > 0 && candidate.depth == param.max_depth)
|| (param.max_leaves > 0 && num_leaves == param.max_leaves) ) {
(*p_tree)[nid].set_leaf(snode[nid].weight * param.learning_rate);
} else {
tstart = dmlc::GetTime();
this->ApplySplit(nid, gmat, column_matrix, hist_, *p_fmat, p_tree);
time_apply_split += dmlc::GetTime() - tstart;
tstart = dmlc::GetTime();
xgboost/src/tree/updater_fast_hist.cc view on Meta::CPAN
tstart = dmlc::GetTime();
this->InitNewNode(cleft, gmat, gpair, *p_fmat, *p_tree);
this->InitNewNode(cright, gmat, gpair, *p_fmat, *p_tree);
time_init_new_node += dmlc::GetTime() - tstart;
tstart = dmlc::GetTime();
this->EvaluateSplit(cleft, gmat, hist_, *p_fmat, *p_tree, feat_set);
this->EvaluateSplit(cright, gmat, hist_, *p_fmat, *p_tree, feat_set);
time_evaluate_split += dmlc::GetTime() - tstart;
qexpand_->push(ExpandEntry(cleft, p_tree->GetDepth(cleft),
snode[cleft].best.loss_chg,
timestamp++));
qexpand_->push(ExpandEntry(cright, p_tree->GetDepth(cright),
snode[cright].best.loss_chg,
timestamp++));
++num_leaves; // give two and take one, as parent is no longer a leaf
}
}
// set all the rest expanding nodes to leaf
// This post condition is not needed in current code, but may be necessary
// when there are stopping rule that leaves qexpand non-empty
while (!qexpand_->empty()) {
const int nid = qexpand_->top().nid;
qexpand_->pop();
(*p_tree)[nid].set_leaf(snode[nid].weight * param.learning_rate);
}
// remember auxiliary statistics in the tree node
for (int nid = 0; nid < p_tree->param.num_nodes; ++nid) {
p_tree->stat(nid).loss_chg = snode[nid].best.loss_chg;
p_tree->stat(nid).base_weight = snode[nid].weight;
p_tree->stat(nid).sum_hess = static_cast<float>(snode[nid].stats.sum_hess);
snode[nid].stats.SetLeafVec(param, p_tree->leafvec(nid));
}
xgboost/src/tree/updater_fast_hist.cc view on Meta::CPAN
}
}
CHECK_GT(min_nbins_per_feature, 0U);
}
{
snode.reserve(256);
snode.clear();
}
{
if (param.grow_policy == TrainParam::kLossGuide) {
qexpand_.reset(new ExpandQueue(loss_guide));
} else {
qexpand_.reset(new ExpandQueue(depth_wise));
}
}
}
inline void EvaluateSplit(int nid,
const GHistIndexMatrix& gmat,
const HistCollection& hist,
const DMatrix& fmat,
const RegTree& tree,
const std::vector<bst_uint>& feat_set) {
xgboost/src/tree/updater_fast_hist.cc view on Meta::CPAN
// back pointers to tree and data matrix
const RegTree* p_last_tree_;
const DMatrix* p_last_fmat_;
// constraint value
std::vector<TConstraint> constraints_;
typedef std::priority_queue<ExpandEntry,
std::vector<ExpandEntry>,
std::function<bool(ExpandEntry, ExpandEntry)>> ExpandQueue;
std::unique_ptr<ExpandQueue> qexpand_;
enum DataLayout { kDenseDataZeroBased, kDenseDataOneBased, kSparseData };
DataLayout data_layout_;
};
std::unique_ptr<Builder> builder_;
std::unique_ptr<TreeUpdater> pruner_;
};
XGBOOST_REGISTER_TREE_UPDATER(FastHistMaker, "grow_fast_histmaker")
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
for (int depth = 0; depth < param.max_depth; ++depth) {
// reset and propose candidate split
this->ResetPosAndPropose(gpair, p_fmat, fwork_set, *p_tree);
// create histogram
this->CreateHist(gpair, p_fmat, fwork_set, *p_tree);
// find split based on histogram statistics
this->FindSplit(depth, gpair, p_fmat, fwork_set, p_tree);
// reset position after split
this->ResetPositionAfterSplit(p_fmat, *p_tree);
this->UpdateQueueExpand(*p_tree);
// if nothing left to be expand, break
if (qexpand.size() == 0) break;
}
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
(*p_tree)[nid].set_leaf(p_tree->stat(nid).base_weight * param.learning_rate);
}
}
// this function does two jobs
// (1) reset the position in array position, to be the latest leaf id
// (2) propose a set of candidate cuts and set wspace.rptr wspace.cut correctly
virtual void ResetPosAndPropose(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector <bst_uint> &fset,
const RegTree &tree) = 0;
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
}
}
}
inline void FindSplit(int depth,
const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector <bst_uint> &fset,
RegTree *p_tree) {
const size_t num_feature = fset.size();
// get the best split condition for each node
std::vector<SplitEntry> sol(qexpand.size());
std::vector<TStats> left_sum(qexpand.size());
bst_omp_uint nexpand = static_cast<bst_omp_uint>(qexpand.size());
#pragma omp parallel for schedule(dynamic, 1)
for (bst_omp_uint wid = 0; wid < nexpand; ++wid) {
const int nid = qexpand[wid];
CHECK_EQ(node2workindex[nid], static_cast<int>(wid));
SplitEntry &best = sol[wid];
TStats &node_sum = wspace.hset[0][num_feature + wid * (num_feature + 1)].data[0];
for (size_t i = 0; i < fset.size(); ++i) {
EnumerateSplit(this->wspace.hset[0][i + wid * (num_feature+1)],
node_sum, fset[i], &best, &left_sum[wid]);
}
}
// get the best result, we can synchronize the solution
for (bst_omp_uint wid = 0; wid < nexpand; ++wid) {
const int nid = qexpand[wid];
const SplitEntry &best = sol[wid];
const TStats &node_sum = wspace.hset[0][num_feature + wid * (num_feature + 1)].data[0];
this->SetStats(p_tree, nid, node_sum);
// set up the values
p_tree->stat(nid).loss_chg = best.loss_chg;
// now we know the solution in snode[nid], set split
if (best.loss_chg > rt_eps) {
p_tree->AddChilds(nid);
(*p_tree)[nid].set_split(best.split_index(),
best.split_value, best.default_left());
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
if (offset >= 0) {
this->UpdateHistCol(gpair, batch[i], info, tree,
fset, offset,
&thread_hist[omp_get_thread_num()]);
}
}
}
// update node statistics.
this->GetNodeStats(gpair, *p_fmat, tree,
&thread_stats, &node_stats);
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
const int wid = this->node2workindex[nid];
this->wspace.hset[0][fset.size() + wid * (fset.size()+1)]
.data[0] = node_stats[nid];
}
};
// sync the histogram
// if it is C++11, use lazy evaluation for Allreduce
#if __cplusplus >= 201103L
this->histred.Allreduce(dmlc::BeginPtr(this->wspace.hset[0].data),
this->wspace.hset[0].data.size(), lazy_get_hist);
#else
this->histred.Allreduce(dmlc::BeginPtr(this->wspace.hset[0].data),
this->wspace.hset[0].data.size());
#endif
}
void ResetPositionAfterSplit(DMatrix *p_fmat,
const RegTree &tree) override {
this->GetSplitSet(this->qexpand, tree, &fsplit_set);
}
void ResetPosAndPropose(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector<bst_uint> &fset,
const RegTree &tree) override {
const MetaInfo &info = p_fmat->info();
// fill in reverse map
feat2workindex.resize(tree.param.num_feature);
std::fill(feat2workindex.begin(), feat2workindex.end(), -1);
work_set.clear();
for (size_t i = 0; i < fset.size(); ++i) {
if (feat_helper.Type(fset[i]) == 2) {
feat2workindex[fset[i]] = static_cast<int>(work_set.size());
work_set.push_back(fset[i]);
} else {
feat2workindex[fset[i]] = -2;
}
}
const size_t work_set_size = work_set.size();
sketchs.resize(this->qexpand.size() * work_set_size);
for (size_t i = 0; i < sketchs.size(); ++i) {
sketchs[i].Init(info.num_row, this->param.sketch_eps);
}
// intitialize the summary array
summary_array.resize(sketchs.size());
// setup maximum size
unsigned max_size = this->param.max_sketch_size();
for (size_t i = 0; i < sketchs.size(); ++i) {
summary_array[i].Reserve(max_size);
}
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
CHECK_EQ(summary_array.size(), sketchs.size());
}
if (summary_array.size() != 0) {
size_t nbytes = WXQSketch::SummaryContainer::CalcMemCost(max_size);
sreducer.Allreduce(dmlc::BeginPtr(summary_array), nbytes, summary_array.size());
}
// now we get the final result of sketch, setup the cut
this->wspace.cut.clear();
this->wspace.rptr.clear();
this->wspace.rptr.push_back(0);
for (size_t wid = 0; wid < this->qexpand.size(); ++wid) {
for (size_t i = 0; i < fset.size(); ++i) {
int offset = feat2workindex[fset[i]];
if (offset >= 0) {
const WXQSketch::Summary &a = summary_array[wid * work_set_size + offset];
for (size_t i = 1; i < a.size; ++i) {
bst_float cpt = a.data[i].value - rt_eps;
if (i == 1 || cpt > this->wspace.cut.back()) {
this->wspace.cut.push_back(cpt);
}
}
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
bst_float cpt = feat_helper.MaxValue(fset[i]);
this->wspace.cut.push_back(cpt + fabs(cpt) + rt_eps);
this->wspace.rptr.push_back(static_cast<unsigned>(this->wspace.cut.size()));
}
}
// reserve last value for global statistics
this->wspace.cut.push_back(0.0f);
this->wspace.rptr.push_back(static_cast<unsigned>(this->wspace.cut.size()));
}
CHECK_EQ(this->wspace.rptr.size(),
(fset.size() + 1) * this->qexpand.size() + 1);
}
inline void UpdateHistCol(const std::vector<bst_gpair> &gpair,
const ColBatch::Inst &c,
const MetaInfo &info,
const RegTree &tree,
const std::vector<bst_uint> &fset,
bst_uint fid_offset,
std::vector<HistEntry> *p_temp) {
if (c.length == 0) return;
// initialize sbuilder for use
std::vector<HistEntry> &hbuilder = *p_temp;
hbuilder.resize(tree.param.num_nodes);
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const unsigned nid = this->qexpand[i];
const unsigned wid = this->node2workindex[nid];
hbuilder[nid].istart = 0;
hbuilder[nid].hist = this->wspace.hset[0][fid_offset + wid * (fset.size()+1)];
}
if (TStats::kSimpleStats != 0 && this->param.cache_opt != 0) {
const bst_uint kBuffer = 32;
bst_uint align_length = c.length / kBuffer * kBuffer;
int buf_position[kBuffer];
bst_gpair buf_gpair[kBuffer];
for (bst_uint j = 0; j < align_length; j += kBuffer) {
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
inline void UpdateSketchCol(const std::vector<bst_gpair> &gpair,
const ColBatch::Inst &c,
const RegTree &tree,
size_t work_set_size,
bst_uint offset,
std::vector<BaseMaker::SketchEntry> *p_temp) {
if (c.length == 0) return;
// initialize sbuilder for use
std::vector<BaseMaker::SketchEntry> &sbuilder = *p_temp;
sbuilder.resize(tree.param.num_nodes);
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const unsigned nid = this->qexpand[i];
const unsigned wid = this->node2workindex[nid];
sbuilder[nid].sum_total = 0.0f;
sbuilder[nid].sketch = &sketchs[wid * work_set_size + offset];
}
// first pass, get sum of weight, TODO, optimization to skip first pass
for (bst_uint j = 0; j < c.length; ++j) {
const bst_uint ridx = c[j].index;
const int nid = this->position[ridx];
if (nid >= 0) {
sbuilder[nid].sum_total += gpair[ridx].hess;
}
}
// if only one value, no need to do second pass
if (c[0].fvalue == c[c.length-1].fvalue) {
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
sbuilder[nid].sketch->Push(c[0].fvalue, static_cast<bst_float>(sbuilder[nid].sum_total));
}
return;
}
// two pass scan
unsigned max_size = this->param.max_sketch_size();
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
sbuilder[nid].Init(max_size);
}
// second pass, build the sketch
if (TStats::kSimpleStats != 0 && this->param.cache_opt != 0) {
const bst_uint kBuffer = 32;
bst_uint align_length = c.length / kBuffer * kBuffer;
int buf_position[kBuffer];
bst_float buf_hess[kBuffer];
for (bst_uint j = 0; j < align_length; j += kBuffer) {
for (bst_uint i = 0; i < kBuffer; ++i) {
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
}
} else {
for (bst_uint j = 0; j < c.length; ++j) {
const bst_uint ridx = c[j].index;
const int nid = this->position[ridx];
if (nid >= 0) {
sbuilder[nid].Push(c[j].fvalue, gpair[ridx].hess, max_size);
}
}
}
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
sbuilder[nid].Finalize(max_size);
}
}
// cached dmatrix where we initialized the feature on.
const DMatrix* cache_dmatrix_;
// feature helper
BaseMaker::FMetaHelper feat_helper;
// temp space to map feature id to working index
std::vector<int> feat2workindex;
// set of index from fset that are current work set
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
};
// global proposal
template<typename TStats>
class GlobalProposalHistMaker: public CQHistMaker<TStats> {
protected:
void ResetPosAndPropose(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector<bst_uint> &fset,
const RegTree &tree) override {
if (this->qexpand.size() == 1) {
cached_rptr_.clear();
cached_cut_.clear();
}
if (cached_rptr_.size() == 0) {
CHECK_EQ(this->qexpand.size(), 1U);
CQHistMaker<TStats>::ResetPosAndPropose(gpair, p_fmat, fset, tree);
cached_rptr_ = this->wspace.rptr;
cached_cut_ = this->wspace.cut;
} else {
this->wspace.cut.clear();
this->wspace.rptr.clear();
this->wspace.rptr.push_back(0);
for (size_t i = 0; i < this->qexpand.size(); ++i) {
for (size_t j = 0; j < cached_rptr_.size() - 1; ++j) {
this->wspace.rptr.push_back(
this->wspace.rptr.back() + cached_rptr_[j + 1] - cached_rptr_[j]);
}
this->wspace.cut.insert(this->wspace.cut.end(), cached_cut_.begin(), cached_cut_.end());
}
CHECK_EQ(this->wspace.rptr.size(),
(fset.size() + 1) * this->qexpand.size() + 1);
CHECK_EQ(this->wspace.rptr.back(), this->wspace.cut.size());
}
}
// code to create histogram
void CreateHist(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector<bst_uint> &fset,
const RegTree &tree) override {
const MetaInfo &info = p_fmat->info();
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
this->UpdateHistCol(gpair, batch[i], info, tree,
fset, offset,
&this->thread_hist[omp_get_thread_num()]);
}
}
}
// update node statistics.
this->GetNodeStats(gpair, *p_fmat, tree,
&(this->thread_stats), &(this->node_stats));
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
const int wid = this->node2workindex[nid];
this->wspace.hset[0][fset.size() + wid * (fset.size()+1)]
.data[0] = this->node_stats[nid];
}
}
this->histred.Allreduce(dmlc::BeginPtr(this->wspace.hset[0].data),
this->wspace.hset[0].data.size());
}
// cached unit pointer
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
class QuantileHistMaker: public HistMaker<TStats> {
protected:
typedef common::WXQuantileSketch<bst_float, bst_float> WXQSketch;
void ResetPosAndPropose(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const std::vector <bst_uint> &fset,
const RegTree &tree) override {
const MetaInfo &info = p_fmat->info();
// initialize the data structure
const int nthread = omp_get_max_threads();
sketchs.resize(this->qexpand.size() * tree.param.num_feature);
for (size_t i = 0; i < sketchs.size(); ++i) {
sketchs[i].Init(info.num_row, this->param.sketch_eps);
}
// start accumulating statistics
dmlc::DataIter<RowBatch> *iter = p_fmat->RowIterator();
iter->BeforeFirst();
while (iter->Next()) {
const RowBatch &batch = iter->Value();
// parallel convert to column major format
common::ParallelGroupBuilder<SparseBatch::Entry>
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
summary_array[i].Reserve(max_size);
summary_array[i].SetPrune(out, max_size);
}
size_t nbytes = WXQSketch::SummaryContainer::CalcMemCost(max_size);
sreducer.Allreduce(dmlc::BeginPtr(summary_array), nbytes, summary_array.size());
// now we get the final result of sketch, setup the cut
this->wspace.cut.clear();
this->wspace.rptr.clear();
this->wspace.rptr.push_back(0);
for (size_t wid = 0; wid < this->qexpand.size(); ++wid) {
for (int fid = 0; fid < tree.param.num_feature; ++fid) {
const WXQSketch::Summary &a = summary_array[wid * tree.param.num_feature + fid];
for (size_t i = 1; i < a.size; ++i) {
bst_float cpt = a.data[i].value - rt_eps;
if (i == 1 || cpt > this->wspace.cut.back()) {
this->wspace.cut.push_back(cpt);
}
}
// push a value that is greater than anything
if (a.size != 0) {
xgboost/src/tree/updater_histmaker.cc view on Meta::CPAN
bst_float last = cpt + fabs(cpt) + rt_eps;
this->wspace.cut.push_back(last);
}
this->wspace.rptr.push_back(this->wspace.cut.size());
}
// reserve last value for global statistics
this->wspace.cut.push_back(0.0f);
this->wspace.rptr.push_back(this->wspace.cut.size());
}
CHECK_EQ(this->wspace.rptr.size(),
(tree.param.num_feature + 1) * this->qexpand.size() + 1);
}
private:
// summary array
std::vector<WXQSketch::SummaryContainer> summary_array;
// reducer for summary
rabit::SerializeReducer<WXQSketch::SummaryContainer> sreducer;
// local temp column data structure
std::vector<size_t> col_ptr;
// local storage of column data
xgboost/src/tree/updater_skmaker.cc view on Meta::CPAN
inline void Update(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
RegTree *p_tree) {
this->InitData(gpair, *p_fmat, *p_tree);
for (int depth = 0; depth < param.max_depth; ++depth) {
this->GetNodeStats(gpair, *p_fmat, *p_tree,
&thread_stats, &node_stats);
this->BuildSketch(gpair, p_fmat, *p_tree);
this->SyncNodeStats();
this->FindSplit(depth, gpair, p_fmat, p_tree);
this->ResetPositionCol(qexpand, p_fmat, *p_tree);
this->UpdateQueueExpand(*p_tree);
// if nothing left to be expand, break
if (qexpand.size() == 0) break;
}
if (qexpand.size() != 0) {
this->GetNodeStats(gpair, *p_fmat, *p_tree,
&thread_stats, &node_stats);
this->SyncNodeStats();
}
// set all statistics correctly
for (int nid = 0; nid < p_tree->param.num_nodes; ++nid) {
this->SetStats(nid, node_stats[nid], p_tree);
if (!(*p_tree)[nid].is_leaf()) {
p_tree->stat(nid).loss_chg = static_cast<bst_float>(
node_stats[(*p_tree)[nid].cleft()].CalcGain(param) +
node_stats[(*p_tree)[nid].cright()].CalcGain(param) -
node_stats[nid].CalcGain(param));
}
}
// set left leaves
for (size_t i = 0; i < qexpand.size(); ++i) {
const int nid = qexpand[i];
(*p_tree)[nid].set_leaf(p_tree->stat(nid).base_weight * param.learning_rate);
}
}
// define the sketch we want to use
typedef common::WXQuantileSketch<bst_float, bst_float> WXQSketch;
private:
// statistics needed in the gradient calculation
struct SKStats {
/*! \brief sum of all positive gradient */
xgboost/src/tree/updater_skmaker.cc view on Meta::CPAN
a.Add(b);
}
/*! \brief set leaf vector value based on statistics */
inline void SetLeafVec(const TrainParam ¶m, bst_float *vec) const {
}
};
inline void BuildSketch(const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
const RegTree &tree) {
const MetaInfo& info = p_fmat->info();
sketchs.resize(this->qexpand.size() * tree.param.num_feature * 3);
for (size_t i = 0; i < sketchs.size(); ++i) {
sketchs[i].Init(info.num_row, this->param.sketch_eps);
}
thread_sketch.resize(omp_get_max_threads());
// number of rows in
const size_t nrows = p_fmat->buffered_rowset().size();
// start accumulating statistics
dmlc::DataIter<ColBatch> *iter = p_fmat->ColIterator();
iter->BeforeFirst();
while (iter->Next()) {
xgboost/src/tree/updater_skmaker.cc view on Meta::CPAN
const ColBatch::Inst &c,
const RegTree &tree,
const std::vector<SKStats> &nstats,
bst_uint fid,
bool col_full,
std::vector<SketchEntry> *p_temp) {
if (c.length == 0) return;
// initialize sbuilder for use
std::vector<SketchEntry> &sbuilder = *p_temp;
sbuilder.resize(tree.param.num_nodes * 3);
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const unsigned nid = this->qexpand[i];
const unsigned wid = this->node2workindex[nid];
for (int k = 0; k < 3; ++k) {
sbuilder[3 * nid + k].sum_total = 0.0f;
sbuilder[3 * nid + k].sketch = &sketchs[(wid * tree.param.num_feature + fid) * 3 + k];
}
}
if (!col_full) {
for (bst_uint j = 0; j < c.length; ++j) {
const bst_uint ridx = c[j].index;
const int nid = this->position[ridx];
xgboost/src/tree/updater_skmaker.cc view on Meta::CPAN
const bst_gpair &e = gpair[ridx];
if (e.grad >= 0.0f) {
sbuilder[3 * nid + 0].sum_total += e.grad;
} else {
sbuilder[3 * nid + 1].sum_total -= e.grad;
}
sbuilder[3 * nid + 2].sum_total += e.hess;
}
}
} else {
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const unsigned nid = this->qexpand[i];
sbuilder[3 * nid + 0].sum_total = static_cast<bst_float>(nstats[nid].pos_grad);
sbuilder[3 * nid + 1].sum_total = static_cast<bst_float>(nstats[nid].neg_grad);
sbuilder[3 * nid + 2].sum_total = static_cast<bst_float>(nstats[nid].sum_hess);
}
}
// if only one value, no need to do second pass
if (c[0].fvalue == c[c.length-1].fvalue) {
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
for (int k = 0; k < 3; ++k) {
sbuilder[3 * nid + k].sketch->Push(c[0].fvalue,
static_cast<bst_float>(
sbuilder[3 * nid + k].sum_total));
}
}
return;
}
// two pass scan
unsigned max_size = param.max_sketch_size();
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
for (int k = 0; k < 3; ++k) {
sbuilder[3 * nid + k].Init(max_size);
}
}
// second pass, build the sketch
for (bst_uint j = 0; j < c.length; ++j) {
const bst_uint ridx = c[j].index;
const int nid = this->position[ridx];
if (nid >= 0) {
const bst_gpair &e = gpair[ridx];
if (e.grad >= 0.0f) {
sbuilder[3 * nid + 0].Push(c[j].fvalue, e.grad, max_size);
} else {
sbuilder[3 * nid + 1].Push(c[j].fvalue, -e.grad, max_size);
}
sbuilder[3 * nid + 2].Push(c[j].fvalue, e.hess, max_size);
}
}
for (size_t i = 0; i < this->qexpand.size(); ++i) {
const int nid = this->qexpand[i];
for (int k = 0; k < 3; ++k) {
sbuilder[3 * nid + k].Finalize(max_size);
}
}
}
inline void SyncNodeStats(void) {
CHECK_NE(qexpand.size(), 0U);
std::vector<SKStats> tmp(qexpand.size());
for (size_t i = 0; i < qexpand.size(); ++i) {
tmp[i] = node_stats[qexpand[i]];
}
stats_reducer.Allreduce(dmlc::BeginPtr(tmp), tmp.size());
for (size_t i = 0; i < qexpand.size(); ++i) {
node_stats[qexpand[i]] = tmp[i];
}
}
inline void FindSplit(int depth,
const std::vector<bst_gpair> &gpair,
DMatrix *p_fmat,
RegTree *p_tree) {
const bst_uint num_feature = p_tree->param.num_feature;
// get the best split condition for each node
std::vector<SplitEntry> sol(qexpand.size());
bst_omp_uint nexpand = static_cast<bst_omp_uint>(qexpand.size());
#pragma omp parallel for schedule(dynamic, 1)
for (bst_omp_uint wid = 0; wid < nexpand; ++wid) {
const int nid = qexpand[wid];
CHECK_EQ(node2workindex[nid], static_cast<int>(wid));
SplitEntry &best = sol[wid];
for (bst_uint fid = 0; fid < num_feature; ++fid) {
unsigned base = (wid * p_tree->param.num_feature + fid) * 3;
EnumerateSplit(summary_array[base + 0],
summary_array[base + 1],
summary_array[base + 2],
node_stats[nid], fid, &best);
}
}
// get the best result, we can synchronize the solution
for (bst_omp_uint wid = 0; wid < nexpand; ++wid) {
const int nid = qexpand[wid];
const SplitEntry &best = sol[wid];
// set up the values
p_tree->stat(nid).loss_chg = best.loss_chg;
this->SetStats(nid, node_stats[nid], p_tree);
// now we know the solution in snode[nid], set split
if (best.loss_chg > rt_eps) {
p_tree->AddChilds(nid);
(*p_tree)[nid].set_split(best.split_index(),
best.split_value, best.default_left());
// mark right child as 0, to indicate fresh leaf
( run in 0.890 second using v1.01-cache-2.11-cpan-5b529ec07f3 )