Sum of hessians calculated incorrectly under hist method
- 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