本記事では、勾配ブースティング（Gradient Boosting）を用いたマルチクラス分類器、GBDT（Gradient Boosting Decision Tree）の仕組みについて実装コードとともに解説します。
ここでは、回帰木を基本ブロックとして用い、各ブースティングステップで残差（疑似勾配）を学習することで、多クラスのロジスティック損失を最小化する方法について説明します。
GBDTとは？
GBDTは、複数の回帰木を逐次的に学習させ、それぞれの出力を組み合わせることで強力な予測モデルを構築するブースティング手法です。
マルチクラス分類の場合、各クラスごとに残差を計算し、各ブースティングイテレーションでクラスごとの回帰木を学習して更新していきます。
GBDTの主要な特徴は以下の通りです。
- 逐次的な学習:
各ブースティングステップでは、前のステップまでの誤差（疑似残差）に基づいて新たな回帰木を学習し、予測値を更新します。 - 学習率 (learning rate):
各木の寄与度を調整するパラメータで、学習率が低いほど各木の影響は小さくなりますが、安定した収束が期待されます。 - 多クラス対応:
各クラスに対して回帰木を個別に学習し、最終的な予測はソフトマックス関数を用いてクラス確率として算出されます。
2. 実装の概要
今回の実装では、以下の3つの主要なコンポーネントでGBDTを構築しています。
- 回帰木用ノード (
Nodeクラス):
回帰木の各ノードの構造を定義し、分割に用いる特徴や閾値、左右の子ノード、または葉ノードの場合は予測値を保持します。 - 回帰木 (
DecisionTreeRegressorクラス):
分割基準として分散（または二乗誤差）を用い、再帰的に木を成長させます。
葉ノードでは対象変数の平均値を予測値として返します。 - GBDT分類器 (
GBDTClassifierクラス):
マルチクラス分類に対応するため、各ブースティングステップで各クラスごとに回帰木を学習します。
初期予測として各クラスの対数尤度（log probability）を用い、各ステップで残差（疑似勾配）を学習し、学習率を乗じて予測値を更新します。
3. 回帰木の実装
まずは、回帰木の実装について説明します。
この回帰木は、各ノードでランダムに選択した特徴量から最適な分割を見つけ、分割後の各領域の分散（×サンプル数）の和が最小になるように学習します。
コード例: NodeクラスとDecisionTreeRegressorの一部
class Node:
def __init__(self, feature_index=None, threshold=None, left=None, right=None, *, value=None):
"""
A Node in the decision tree.
- feature_index: 分割に使用する特徴のインデックス
- threshold: 分割の閾値
- left, right: 左右の子ノード
- value: 葉ノードの場合の予測値
"""
self.feature_index = feature_index
self.threshold = threshold
self.left = left
self.right = right
self.value = value
def is_leaf_node(self):
return self.value is not None
class DecisionTreeRegressor:
def __init__(self, min_samples_split=2, max_depth=100, n_features=None):
self.min_samples_split = min_samples_split
self.max_depth = max_depth
self.n_features = n_features
self.root = None
def fit(self, X, y):
self.n_features_ = X.shape[1]
if self.n_features is None:
self.n_features = self.n_features_
self.root = self._grow_tree(X, y)
def _grow_tree(self, X, y, depth=0):
n_samples, n_features = X.shape
if depth >= self.max_depth or n_samples < self.min_samples_split:
leaf_value = self._calculate_leaf_value(y)
return Node(value=leaf_value)
feature_idxs = np.random.choice(n_features, self.n_features, replace=False)
best_feat, best_thresh, best_loss = None, None, float("inf")
for feat_idx in feature_idxs:
X_column = X[:, feat_idx]
thresholds = np.unique(X_column)
for threshold in thresholds:
left_mask = X_column <= threshold
right_mask = X_column > threshold
if np.sum(left_mask) == 0 or np.sum(right_mask) == 0:
continue
y_left = y[left_mask]
y_right = y[right_mask]
loss = np.var(y_left) * len(y_left) + np.var(y_right) * len(y_right)
if loss < best_loss:
best_loss = loss
best_feat = feat_idx
best_thresh = threshold
if best_feat is None:
leaf_value = self._calculate_leaf_value(y)
return Node(value=leaf_value)
left_mask = X[:, best_feat] <= best_thresh
right_mask = X[:, best_feat] > best_thresh
left = self._grow_tree(X[left_mask], y[left_mask], depth + 1)
right = self._grow_tree(X[right_mask], y[right_mask], depth + 1)
return Node(feature_index=best_feat, threshold=best_thresh, left=left, right=right)
def _calculate_leaf_value(self, y):
return np.mean(y)
def predict(self, X):
return np.array([self._traverse_tree(x, self.root) for x in X])
def _traverse_tree(self, x, node):
if node.is_leaf_node():
return node.value
if x[node.feature_index] <= node.threshold:
return self._traverse_tree(x, node.left)
else:
return self._traverse_tree(x, node.right)
上記コードでは、ノードの生成、最適な分割閾値の探索、葉ノードの値として対象変数の平均値を使用する点などが実装されています。
4. GBDT分類器の実装
GBDT分類器は、回帰木を用いてマルチクラス分類を実現するために、以下の手順で学習を進めます。
- 初期予測の設定:
各クラスの初期予測値として、各クラスの出現確率の対数（log probability）を用います。 - 疑似残差の計算:
ソフトマックス関数を用いて各サンプルのクラス確率を計算し、実際のクラス（one-hot表現）との差分を疑似残差として求めます。 - 各ブースティングステップでの更新:
各クラスごとに回帰木を学習し、疑似残差を予測します。
予測値に学習率を掛け合わせた値を各クラスの予測に加算し、モデル全体の出力を更新します。 - 最終予測:
最終的な出力に対してソフトマックス関数を適用し、各クラスの確率を算出します。
その後、最も高い確率を持つクラスを最終予測とします。
コード例: GBDTClassifier の主要部分
class GBDTClassifier:
def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3, min_samples_split=2):
self.n_estimators = n_estimators
self.learning_rate = learning_rate
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.n_classes = None
self.trees = [] # 各イテレーションでのクラスごとの回帰木のリスト
self.initial_predictions = None # 各クラスの初期予測
def fit(self, X, y):
n_samples = X.shape[0]
self.n_classes = np.unique(y).size
# one-hot encoding の生成
Y = np.zeros((n_samples, self.n_classes))
for i, label in enumerate(y):
Y[i, label] = 1
# 各クラスの初期予測（log probability）
class_probs = np.bincount(y, minlength=self.n_classes) / n_samples
eps = 1e-10
self.initial_predictions = np.log(np.clip(class_probs, eps, 1 - eps))
F = np.tile(self.initial_predictions, (n_samples, 1))
# ブースティングイテレーション
for m in range(self.n_estimators):
exp_F = np.exp(F)
sum_exp_F = np.sum(exp_F, axis=1, keepdims=True)
P = exp_F / sum_exp_F # サンプルごとの各クラスの確率
residuals = Y - P
trees_per_class = []
for k in range(self.n_classes):
tree = DecisionTreeRegressor(min_samples_split=self.min_samples_split,
max_depth=self.max_depth)
tree.fit(X, residuals[:, k])
update = tree.predict(X)
F[:, k] += self.learning_rate * update
trees_per_class.append(tree)
self.trees.append(trees_per_class)
def predict_proba(self, X):
n_samples = X.shape[0]
F = np.tile(self.initial_predictions, (n_samples, 1))
for trees_per_class in self.trees:
for k, tree in enumerate(trees_per_class):
F[:, k] += self.learning_rate * tree.predict(X)
exp_F = np.exp(F)
sum_exp_F = np.sum(exp_F, axis=1, keepdims=True)
proba = exp_F / sum_exp_F
return proba
def predict(self, X):
proba = self.predict_proba(X)
return np.argmax(proba, axis=1)
上記コードでは、各イテレーションごとに各クラスの回帰木を学習し、更新後の予測値に基づいてソフトマックス確率を計算しています。
5. まとめ
本記事では、回帰木を基本としたGBDTによるマルチクラス分類器の実装方法とその背景について解説しました。
- 回帰木を用いて分割基準（分散の最小化）に基づくツリーを構築し、
- 勾配ブースティングにより各ステップで疑似残差を学習、更新することで、
- ソフトマックス関数を用いて最終的なクラス確率を算出する手法となります。
この実装は、GBDTの基本概念を理解するための基本的な実装例です。
XGBoostやLightGBM等にはこれに種々の工夫が加えられています。
この記事がGBDTの基礎を知るきっかけとなれば幸いです。
コメント