dmlc / dmlc/xgboost

Sum of hessians calculated incorrectly under hist method

Open
#12,248 19 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
28.8k
Forks
8.9k
Avg merge
1d 12h
Merged PRs (30d)
54

Description

When running with the `hist` tree method which is now default, if one manually splits the data according to the information in the trees, one would see that the sum of hessians would not always match with what one would get by passing observations down the trees.

In the case of squared error, the hessians are always equal to one, so their sum is equal to the number of rows, which makes it easy to make the calculations.

Example where there would be some slight mismatches:
```python
import xgboost as xgb
import treelite
from sklearn.datasets import fetch_california_housing
import numpy as np
import polars as pl
import json

tmp = fetch_california_housing()
X = pl.DataFrame(tmp.data, schema=tmp.feature_names)
y = tmp.target

model = xgb.train(
dtrain=xgb.DMatrix(X, y),
num_boost_round=1,
params={
"objective": "reg:squarederror",
"seed": 123,
"tree_method": "hist",
}
)
tl_model = treelite.frontend.from_xgboost(model)
tl_json = json.loads(tl_model.dump_as_json())

def assign_nrows_to_json():
curr_node = 0
curr_X = tmp.data
assign_nrows_to_json_recursive(curr_node, curr_X, tl_json["trees"][0]["nodes"])

def assign_nrows_to_json_recursive(
curr_node: int,
curr_X: np.ndarray,
tl_json_nodes: dict,
):
node_info = tl_json_nodes[curr_node]
node_info["n_rows"] = curr_X.shape[0]
if "leaf_value" in node_info:
return

val = curr_X[:, node_info["split_feature_id"]]
thr = node_info["threshold"]
if node_info["comparison_op"] == "<":
mask_left = val < thr
elif node_info["comparison_op"] == "<=":
mask_left = val <= thr
elif node_info["comparison_op"] == ">":
mask_left = val > thr
elif node_info["comparison_op"] == ">=":
mask_left = val >= thr

left_X = curr_X[mask_left]
right_X = curr_X[~mask_left]
assign_nrows_to_json_recursive(
node_info["left_child"],
left_X,
tl_json_nodes,
)
assign_nrows_to_json_recursive(
node_info["right_child"],
right_X,
tl_json_nodes,
)

assign_nrows_to_json()

nodes_df = pl.DataFrame(tl_json["trees"][0]["nodes"])

display(
nodes_df
.filter(
pl.col("sum_hess") != pl.col("n_rows")
)
)
```
shape: (44, 12)
node_id | split_feature_id | default_left | node_type | comparison_op | threshold | left_child | right_child | sum_hess | gain | n_rows | leaf_value
-- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | --
i64 | i64 | bool | str | str | f64 | i64 | i64 | f64 | f64 | i64 | f64
5 | 5 | false | "numerical_test_node" | "<" | 2.746993 | 11 | 12 | 3056.0 | 506.611816 | 3057 | null
6 | 0 | false | "numerical_test_node" | "<" | 7.8239 | 13 | 14 | 1335.0 | 222.381836 | 1334 | null
7 | 0 | false | "numerical_test_node" | "<" | 2.2174 | 15 | 16 | 3436.0 | 245.249878 | 3441 | null
8 | 0 | false | "numerical_test_node" | "<" | 2.4167 | 17 | 18 | 4617.0 | 191.924561 | 4612 | null
11 | 1 | false | "numerical_test_node" | "<" | 20.0 | 23 | 24 | 1270.0 | 119.098389 | 1271 | null
… | … | … | … | … | … | … | … | … | … | … | …
104 | null | null | null | null | null | null | null | 205.0 | null | 206 | 0.046349
109 | null | null | null | null | null | null | null | 388.0 | null | 387 | 0.161952
123 | null | null | null | null | null | null | null | 3.0 | null | 4 | -0.159801
124 | null | null | null | null | null | null | null | 15.0 | null | 14 | 0.511588
125 | null | null | null | null | null | null | null | 518.0 | null | 517 | 0.812895

If one were to change `tree_method` to `exact` in the code above, it would return an empty table as expected.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by running the provided Python reproduction with XGBoost's `hist` and `exact` tree methods, then compare each node's `sum_hess` with the rows routed through the dumped tree. Trace the histogram method's split-statistic accumulation and verify that the reported sums match the observations reaching each node; done means the mismatches no longer occur under `hist`.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, python
Domain
machine-learning, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.