///|
/// One tree of a LightGBM model, kept in LightGBM's own form: double
/// thresholds and leaf values, `decision_type` flags, and children where a
/// negative index `~i` is leaf `i`.
pub struct LightGBMTree {
split_feature : Array[Int32]
threshold : Array[Double]
decision_type : Array[Int32]
left : Array[Int32]
right : Array[Int32]
leaf_value : Array[Double]
cat_boundaries : Array[Int32]
cat_threshold : Array[UInt32]
}
///|
/// A model saved by LightGBM (`Booster.save_model("model.txt")`, the text
/// format). Predictions follow LightGBM's CPU predictor: every value is a
/// double, trees are added in order, and the result is bit-for-bit what
/// LightGBM's `predict` returns.
pub struct LightGBMModel {
trees : Array[LightGBMTree]
num_class : Int32
/// Trees per boosting round: one per class for `multiclass`, else 1.
num_tree_per_iteration : Int32
num_feature : Int32
/// The objective line as saved, e.g. `binary sigmoid:1`.
objective : String
feature_names : Array[String]
average_output : Bool
priv fast : LgbFast?
// the objective's name and `sigmoid:` parameter, parsed once
priv obj_name : String
priv sigmoid : Double
}
///|
/// LightGBM's `kZeroThreshold` (`1e-35f`): inputs this close to zero are
/// read as zero.
let lgb_zero : Double = Float::from_double(1.0e-35).to_double()
///|
/// Tree fields that loading reads; the rest (gains, counts, weights) are
/// skipped.
fn lgb_tree_key(key : StringView) -> Bool {
match key {
"num_leaves"
| "num_cat"
| "split_feature"
| "threshold"
| "decision_type"
| "left_child"
| "right_child"
| "leaf_value"
| "cat_boundaries"
| "cat_threshold"
| "is_linear" => true
_ => false
}
}
///|
fn lgb_values(
fields : Map[String, StringView],
key : String,
) -> Array[StringView] raise ModelError {
match fields.get(key) {
Some(s) => s.split(" ").filter(x => x != "").to_array()
None => raise InvalidModel("LightGBM tree is missing `\{key}`")
}
}
///|
fn lgb_ints(
fields : Map[String, StringView],
key : String,
) -> Array[Int32] raise ModelError {
let s = match fields.get(key) {
Some(s) => s
None => raise InvalidModel("LightGBM tree is missing `\{key}`")
}
let out = []
let n = s.length()
let mut i = 0
while i < n {
while i < n && s.unsafe_get(i) == ' ' {
i += 1
}
let start = i
let neg = i < n && s.unsafe_get(i) == '-'
if neg {
i += 1
}
let mut v = 0
let mut ok = i < n
while i < n && s.unsafe_get(i) != ' ' {
let c = s.unsafe_get(i).to_int() - '0'.to_int()
if c < 0 || c > 9 || v > 214748364 {
ok = false
}
v = v * 10 + c
i += 1
}
if start == i {
break
}
if i == start + (if neg { 1 } else { 0 }) {
ok = false
}
if !ok {
// not a plain decimal integer: let the general parser judge it
let t = s.unsafe_view(start~, end=i)
out.push(
@string.parse_int(t) catch {
_ => raise InvalidModel("bad integer in `\{key}`: \{t}")
},
)
} else {
out.push(if neg { -v } else { v })
}
}
out
}
///|
fn lgb_doubles(
fields : Map[String, StringView],
key : String,
) -> Array[Double] raise ModelError {
let s = match fields.get(key) {
Some(s) => s
None => raise InvalidModel("LightGBM tree is missing `\{key}`")
}
let out = []
let n = s.length()
let mut i = 0
while i < n {
while i < n && s.unsafe_get(i) == ' ' {
i += 1
}
let start = i
while i < n && s.unsafe_get(i) != ' ' {
i += 1
}
if start == i {
break
}
out.push(
lgb_parse_double(s, start, i) catch {
_ => {
let t = s.unsafe_view(start~, end=i)
raise InvalidModel("bad number in `\{key}`: \{t}")
}
},
)
}
out
}
///|
fn lgb_tree(fields : Map[String, StringView]) -> LightGBMTree raise ModelError {
let num_leaves = lgb_ints(fields, "num_leaves")
if num_leaves.length() != 1 || num_leaves[0] < 1 {
raise InvalidModel("bad `num_leaves`")
}
let n = num_leaves[0]
if fields.get("is_linear") is Some(v) && v.trim(chars=" ") != "0" {
raise Unsupported("LightGBM linear trees")
}
let leaf_value = lgb_doubles(fields, "leaf_value")
if leaf_value.length() != n {
raise InvalidModel("\{leaf_value.length()} leaf values for \{n} leaves")
}
if n == 1 {
return {
split_feature: [],
threshold: [],
decision_type: [],
left: [],
right: [],
leaf_value,
cat_boundaries: [],
cat_threshold: [],
}
}
let split_feature = lgb_ints(fields, "split_feature")
let threshold = lgb_doubles(fields, "threshold")
let decision_type = lgb_ints(fields, "decision_type")
let left = lgb_ints(fields, "left_child")
let right = lgb_ints(fields, "right_child")
let inner = n - 1
for
a in [
split_feature.length(),
threshold.length(),
decision_type.length(),
left.length(),
right.length(),
] {
if a != inner {
raise InvalidModel("tree arrays should have \{inner} entries, got \{a}")
}
}
for c in left + right {
// an internal node index, or ~leaf for a leaf
if c >= inner || c < -n {
raise InvalidModel("child \{c} out of range")
}
}
let num_cat = match fields.get("num_cat") {
Some(_) => lgb_ints(fields, "num_cat")
None => [0]
}
let (cat_boundaries, cat_threshold) = if num_cat.length() == 1 &&
num_cat[0] > 0 {
let b = lgb_ints(fields, "cat_boundaries")
let words = []
for v in lgb_values(fields, "cat_threshold") {
let d = @string.parse_double(v) catch {
_ => raise InvalidModel("bad category bitset word: \{v}")
}
words.push(d.to_uint())
}
if b.length() != num_cat[0] + 1 {
raise InvalidModel(
"`cat_boundaries` should have \{num_cat[0] + 1} entries",
)
}
for i in 0.. b[i + 1] || b[i + 1] > words.length() {
raise InvalidModel("`cat_boundaries` out of range")
}
}
(b, words)
} else {
([], [])
}
for i in 0..= cat_boundaries.length() {
raise InvalidModel("categorical split \{i} has no category set")
}
}
if split_feature[i] < 0 {
raise InvalidModel("negative split feature")
}
}
{
split_feature,
threshold,
decision_type,
left,
right,
leaf_value,
cat_boundaries,
cat_threshold,
}
}
///|
/// Load a LightGBM text model (`Booster.save_model` or `model_to_string`).
/// Numerical and categorical splits, all three missing-value modes, and every
/// built-in objective's output transform are supported; linear trees are not.
pub fn LightGBMModel::from_text(
text : StringView,
) -> LightGBMModel raise ModelError {
let header : Map[String, String] = Map([])
let blocks : Array[Map[String, StringView]] = []
let mut cur : Map[String, StringView]? = None
for raw in text.split("\n") {
let line = raw.trim(chars="\r ")
if line.has_prefix("end of trees") {
break
}
if line.has_prefix("Tree=") {
let m : Map[String, StringView] = Map([])
blocks.push(m)
cur = Some(m)
continue
}
match line.find("=") {
Some(i) => {
let key = line[:i]
match cur {
// a tree keeps only the fields prediction reads, without copying
Some(m) => if lgb_tree_key(key) { m[key.to_owned()] = line[i + 1:] }
None => header[key.to_owned()] = line[i + 1:].to_owned()
}
}
// a bare flag such as `average_output`
None => if cur is None && line != "" { header[line.to_owned()] = "" }
}
}
if header.get("version") is None {
raise InvalidModel("not a LightGBM text model (no `version` line)")
}
let get_int = fn(key : String) -> Int32 raise ModelError {
match header.get(key) {
Some(v) =>
@string.parse_int(v.trim(chars=" ")) catch {
_ => raise InvalidModel("`\{key}` is not an integer: \{v}")
}
None => raise InvalidModel("missing `\{key}`")
}
}
let num_class = get_int("num_class")
let per_iter = get_int("num_tree_per_iteration")
let num_feature = get_int("max_feature_idx") + 1
if num_class < 1 || per_iter < 1 || num_feature < 1 {
raise InvalidModel("bad model header")
}
let trees = []
for b in blocks {
trees.push(lgb_tree(b))
}
if trees.length() % per_iter != 0 {
raise InvalidModel(
"\{trees.length()} trees is not a multiple of \{per_iter} per iteration",
)
}
for t in trees {
for f in t.split_feature {
if f >= num_feature {
raise InvalidModel(
"tree uses feature \{f} but model has \{num_feature}",
)
}
}
}
let objective = header.get("objective").unwrap_or("")
let feature_names = match header.get("feature_names") {
Some(s) =>
s.split(" ").filter(x => x != "").map(x => x.to_owned()).to_array()
None => []
}
{
trees,
num_class,
num_tree_per_iteration: per_iter,
num_feature,
objective,
feature_names,
average_output: header.contains("average_output"),
fast: LgbFast::build(trees, num_feature, per_iter),
obj_name: objective.split(" ").next().map(x => x.to_owned()).unwrap_or(""),
sigmoid: lgb_param(objective, "sigmoid", 1.0),
}
}
///|
/// Leaf reached by `row` (already cleaned by `lgb_row`), as LightGBM's
/// `Tree::GetLeaf` walks it.
fn LightGBMTree::leaf(self : LightGBMTree, row : FixedArray[Double]) -> Int32 {
if self.left.length() == 0 {
return 0
}
let mut node = 0
while node >= 0 {
let d = self.decision_type[node]
let x = row[self.split_feature[node]]
node = if d % 2 == 1 {
// categorical: NaN and negative codes go right; otherwise left when the
// code is in the node's bitset
if x.is_nan() || x.to_int() < 0 {
self.right[node]
} else {
let code = x.to_int()
let k = self.threshold[node].to_int()
let start = self.cat_boundaries[k]
let words = self.cat_boundaries[k + 1] - start
let w = code / 32
if w < words &&
((self.cat_threshold[start + w] >> (code % 32)) & 1) == 1 {
self.left[node]
} else {
self.right[node]
}
}
} else {
let missing = (d >> 2) & 3
let v = if x.is_nan() && missing != 2 { 0.0 } else { x }
if (missing == 1 && v >= -lgb_zero && v <= lgb_zero) ||
(missing == 2 && v.is_nan()) {
if (d & 2) != 0 {
self.left[node]
} else {
self.right[node]
}
} else if v <= self.threshold[node] {
self.left[node]
} else {
self.right[node]
}
}
}
-node - 1
}
///|
/// LightGBM's predictor reads a dense row through its sparse path: values
/// within `kZeroThreshold` of zero become 0, and absent features are 0.
fn LightGBMModel::lgb_row(
self : LightGBMModel,
row : ArrayView[Double],
) -> FixedArray[Double] {
let out = FixedArray::make(self.num_feature, 0.0)
let n = if row.length() < self.num_feature {
row.length()
} else {
self.num_feature
}
for i in 0.. lgb_zero {
out[i] = x
}
}
out
}
///|
/// Raw scores, one per class (`predict(raw_score=True)`): the sum of the
/// trees. Like LightGBM, a random forest's raw score is not averaged.
pub fn LightGBMModel::predict_raw(
self : LightGBMModel,
row : ArrayView[Double],
) -> Array[Double] {
let k = self.num_tree_per_iteration
if self.fast is Some(f) {
let w = f.width()
let ranks = FixedArray::make(if f.by_value { 0 } else { w }, 0)
let values = FixedArray::make(if f.by_value { w } else { 0 }, 0.0)
f.slots_of_doubles(row, ranks, values)
let m = FixedArray::make(k, 0.0)
f.accumulate(ranks, values, 1, m)
return Array::makei(k, i => m[i])
}
let x = self.lgb_row(row)
let out = Array::make(k, 0.0)
for i, t in self.trees {
out[i % k] = out[i % k] + t.leaf_value[t.leaf(x)]
}
out
}
///|
fn lgb_param(objective : String, key : String, default : Double) -> Double {
for part in objective.split(" ") {
if part.has_prefix(key + ":") {
return @string.parse_double(part[key.length() + 1:]) catch {
_ => default
}
}
}
default
}
///|
/// Final predictions (`predict()`): the raw scores, averaged over the rounds
/// for a random forest, then the objective's output transform.
pub fn LightGBMModel::predict(
self : LightGBMModel,
row : ArrayView[Double],
) -> Array[Double] {
let out = self.predict_raw(row)
self.transform(out)
out
}
///|
/// Raw scores to predictions, in place: the average over rounds for a
/// random forest, then the objective's output transform.
fn LightGBMModel::transform(self : LightGBMModel, out : Array[Double]) -> Unit {
let k = self.num_tree_per_iteration
if self.average_output && self.trees.length() > 0 {
let rounds = (self.trees.length() / k).to_double()
for g in 0..
for i in 0.. out[0] = 1.0 / (1.0 + lgb_exp(-out[0]))
"cross_entropy_lambda" => out[0] = @math.ln_1p(lgb_exp(out[0]))
"poisson" | "gamma" | "tweedie" => out[0] = lgb_exp(out[0])
"multiclass" => {
let mut wmax = out[0]
for v in out {
if v > wmax {
wmax = v
}
}
let mut wsum = 0.0
for i in 0.. {
let v = out[0]
out[0] = if v > 0.0 { v * v } else if v < 0.0 { -(v * v) } else { 0.0 }
}
_ => ()
}
}
///|
/// Predictions for every row of `data`, `num_tree_per_iteration` values per
/// row (row-major). Same results as `predict` on each row.
pub fn LightGBMModel::predict_batch(
self : LightGBMModel,
data : DenseMatrix,
) -> Array[Double] {
let k = self.num_tree_per_iteration
let out = Array::make(data.rows * k, 0.0)
match self.fast {
Some(f) if f.heap_depth > 0 && k == 1 => {
let block = 256
let vals = FixedArray::make(block * f.width(), (0.0 : Float))
let m = FixedArray::make(block, 0.0)
let row = [0.0]
let mut start = 0
while start < data.rows {
let n = if data.rows - start < block {
data.rows - start
} else {
block
}
f.float_slots(data.data, data.cols, start, n, vals)
m.fill(0.0)
f.accumulate_fheap(vals, n, m)
for r in 0.. {
// rank blocks of 256 rows reuse each tree from cache four times as
// long; value blocks are eight bytes a slot and stay at 64 rows
let block = if f.by_value { 64 } else { 256 }
let w = f.width()
let ranks = FixedArray::make(if f.by_value { 0 } else { block * w }, 0)
let values = FixedArray::make(if f.by_value { block * w } else { 0 }, 0.0)
let m = FixedArray::make(block * k, 0.0)
let cols = data.cols
let mut start = 0
while start < data.rows {
let n = if data.rows - start < block {
data.rows - start
} else {
block
}
for r in 0..
for r in 0.. x.to_double()))
for g in 0.. Array[Int32] {
let x = self.lgb_row(row)
self.trees.map(t => t.leaf(x))
}
///|
/// Number of trees in the model.
pub fn LightGBMModel::num_trees(self : LightGBMModel) -> Int32 {
self.trees.length()
}