決定木の学習アルゴリズムってどうなってるの？

結論：決定境界の探索はゴリ押し。

二分探索するからオーダーは意外と低いのかな？全てのサンプルに対して勾配を計算するような手法よりは軽いのかな

これが木を作ってる
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L140

add root node
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L214-L225

start, end は自分より下の部分木のインデックスの最初と最後ってことかな。下３つは謎。

分割するかどうか判定
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L244-L254

add node
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L268
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L909

これはなんだ？→各ノードの予測値を設定
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L279

node_value は各ノードに入ってるサンプルのラベルっぽい。
https://github.com/scikit-learn/scikit-learn/blob/2cbf3345bce979b261f7007616cc3465f33a51d3/sklearn/tree/_criterion.pyx#L552
https://github.com/scikit-learn/scikit-learn/blob/2cbf3345bce979b261f7007616cc3465f33a51d3/sklearn/tree/_criterion.pyx#L330-L331

引数で node.value と node_id を足してるところが気持ち悪い

value_stride
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L797

node_value method の引数は、すべての node_value を格納するでかい配列における、とある node の value のインデックスなのかな？

このへんでちらほら出てくる monotonic_cst というのはこういう機能のことらしい
https://scikit-learn.org/stable/auto_examples/ensemble/plot_monotonic_constraints.html

push node on stack
https://github.com/scikit-learn/scikit-learn/blob/4aeb191100f409c880d033683972ab9f47963fa4/sklearn/tree/_tree.pyx#L316-L340

分割するとき、まずこれが呼ばれる
https://github.com/scikit-learn/scikit-learn/blob/e04142cbe0f4f854272f877eb9692053b0a6bcf8/sklearn/tree/_splitter.pyx#L269