///|
/// Integer key of a non-NaN float32 whose order matches float order:
/// `x < y` if and only if `float_key(x) < float_key(y)`. Both zeros map to 0.
/// Keys of finite and infinite floats are all greater than `@kernel.MISSING`.
pub fn float_key(x : Float) -> Int32 {
let b = x.reinterpret_as_int()
if b >= 0 {
b
} else {
-(b & 0x7FFFFFFF)
}
}
///|
/// Key of a categorical feature value, following XGBoost: the value is
/// truncated to an integer code, and negative or too-large codes become -1,
/// which never matches a category and so always goes left.
pub fn category_key(x : Float) -> Int32 {
if x < 0.0 || x >= 2147483648.0 {
-1
} else {
x.to_int()
}
}
///|
/// Every tree of a model packed into one verified `@kernel.Forest`, plus the
/// leaf weights indexed by global node id.
struct Compiled {
forest : @kernel.Forest
offsets : FixedArray[Int32]
leaf_value : FixedArray[Float]
// categorical[j] is true when feature j is used by a categorical split
categorical : FixedArray[Bool]
}
///|
fn compile(
trees : ArrayView[Tree],
num_feature : Int32,
) -> Compiled raise ModelError {
let total = trees.fold(init=0, (acc, t) => acc + t.num_nodes())
let nodes = FixedArray::make(4 * total, 0)
let leaf_value = FixedArray::make(total, (0.0 : Float))
let offsets = FixedArray::make(trees.length(), 0)
let categorical = FixedArray::make(num_feature, false)
let cat_ranges = []
let cats = []
let mut o = 0
for ti, t in trees {
offsets[ti] = o
for i in 0..= num_feature || f >= 0x20000000 {
raise InvalidModel("node \{i} splits on feature \{f} out of range")
}
nodes[4 * g] = t.left[i] + o
nodes[4 * g + 1] = t.right[i] + o
let dl = if t.default_left[i] { 1 } else { 0 }
match t.categories[i] {
None => {
nodes[4 * g + 2] = f * 4 + dl
nodes[4 * g + 3] = float_key(t.value[i])
}
Some(set) => {
categorical[f] = true
nodes[4 * g + 2] = f * 4 + 2 + dl
nodes[4 * g + 3] = cat_ranges.length() / 2
cat_ranges.push(cats.length())
cats.push_iter(set.iter())
cat_ranges.push(cats.length())
}
}
}
o += t.num_nodes()
}
let roots = FixedArray::makei(trees.length(), i => offsets[i])
let forest = @kernel.Forest::new(
nodes,
roots,
FixedArray::from_array(cat_ranges),
FixedArray::from_array(cats),
)
match forest {
Some(forest) => { forest, offsets, leaf_value, categorical, }
None => raise InvalidModel("trees do not form a valid forest")
}
}
///|
/// Fill `out[j]` with the key of `row[j]`.
fn Compiled::encode(
self : Compiled,
row : ArrayView[Float],
out : FixedArray[Int32],
) -> Unit {
for j in 0.. FixedArray[Int32] {
let out = FixedArray::make(row.length(), 0)
self.encode(row, out)
out
}
///|
/// Global leaf node reached by `keys` in tree `t`.
fn Compiled::leaf(
self : Compiled,
t : Int32,
keys : FixedArray[Int32],
) -> Int32 {
self.forest.leaf(t, keys)
}
///|
fn empty_compiled() -> Compiled {
{
forest: @kernel.Forest::new([-1, -1, 0, 0], [0], [], []).unwrap(),
offsets: [0],
leaf_value: [0.0],
categorical: [],
}
}