「機械学習」という言葉がいつ登場したのか、またAIやディープラーニングがどのように発展してきたのかについては、書籍『AI 70年：思考する機械からChatGPTへの道のり』(PR)で紹介しています。

決定木の登場

決定木は、データを「ある条件を満たすか、満たさないか」という分岐によって分類・予測していく手法。結果が木構造として表現されるため、人間にも比較的理解しやすい。機械学習の代表的な手法の一つとして発展してきた。

1980年代には、決定木を実用的なアルゴリズムとして発展させる研究が進んだ。

「CART: Classification and Regression Trees」は、1984年にレオ・ブレイマン（Leo Breiman）らが発表したアルゴリズム。分類だけでなく回帰にも利用できる決定木として、その後の機械学習にも大きな影響を与えた。

「ID3」は、1986年にロス・クィンラン（J. Ross Quinlan）が発表した決定木アルゴリズム。情報利得を利用して、どの特徴量でデータを分割するかを決める。その後、1993年にはクィンランが「C4.5」を発表。ID3を発展させ、より実用的な決定木アルゴリズムとなった。

その後の機械学習では、CART系の決定木をベースにした手法が広く使われるようになった。

決定木は非線形な関係を扱いやすく、データを条件分岐として表現できる一方、1本の木を複雑に育てると過学習しやすいという問題もあった。

こうした決定木の弱点を補うため、複数の木を組み合わせるアンサンブル学習が発展していく。

バギングとブースティング

複数の決定木を組み合わせる方法の一つが、バギング（Bagging）である。

1996年、レオ・ブレイマンは、元のデータからランダムにサンプリングした複数のデータセットを作り、それぞれでモデルを学習させ、予測結果を組み合わせる方法を提案した。

この考え方を決定木に応用し、さらに木を作る際に特徴量もランダムに選ぶことで、木同士の多様性を高めたのが「Random Forest」である。

Random Forestは2001年にブレイマンによって発表され、その後、代表的なアンサンブル学習手法の一つとして広く利用されるようになった。

バギングとは異なる方向から、複数の弱いモデルを組み合わせて予測性能を高める方法も発展した。それがブースティング（Boosting）である。

1990年、ロバート・シャパイアは、弱学習器と強学習器の関係を理論的に研究し、 弱学習器を組み合わせることで強力な学習器を構成できる（予測精度がいまいちなモデルでもうまく組み合わせれば予測精度の高いモデルが作れる）ことを示した。

1995年、ヨーアヴ・フレイントとシャパイアが「AdaBoost」を提案した。

1990年代後半、ジェローム・フリードマンは、ブースティングを "関数空間における勾配降下" として捉える考え方を発展させた。この研究は、のちに「Gradient Boosting（勾配ブースティング）」と呼ばれる手法の基礎となった。1999年、フリードマンがGradient Boostingの考え方を発表し、2001年に論文としてまとめた。

Gradient Boostingでは、前までのモデルの予測誤差をもとに（損失関数の負の勾配を利用して）、次のモデルを追加していく。その際に、決定木を弱学習器として使う代表的な手法が、GBDT（Gradient Boosting Decision Tree：勾配ブースティング決定木）である。

バギング ブースティング
特徴 複数のモデルを独立に作り、その予測を組み合わせる（Bootstrap Aggregating） 複数のモデルを順番に作り、前のモデルの弱点を次のモデルで補っていく（Boosting）
仕組み 元のデータからブートストラップサンプリングで複数の子データを作り、それぞれを使ってモデルを独立に学習する。予測するときは、それぞれのモデルの結果を集めて、多数決（回帰問題では平均）で決める。 まずモデルを作り、その予測結果をもとに、次のモデルを追加する。これを繰り返し、前までのモデルがうまく予測できなかった部分を後のモデルが補っていく。
メリット 複数のモデルの予測を組み合わせることで、個々のモデルのばらつきを抑え、安定した予測を得やすい。モデルを独立して学習できるため、並列計算にも向いている。 複数のモデルを順番に改善していくことで、高い予測性能を狙える。決定木を使ったブースティングでは、複雑な非線形関係や特徴量同士の相互作用も捉えやすい。

正則化

モデルが複雑になりすぎることを抑え、予測を安定させるための考え方。回帰分析では、係数が大きくなりすぎることにペナルティを与える方法が代表的。

説明変数が多くなったり、変数同士の相関が強かったりすると、回帰係数が不安定になることがある。また、モデルが複雑になりすぎると、学習データに過度に適合してしまうこともある。

そこで、予測誤差だけでなく「係数を大きくしすぎない」という条件も同時に考えることで、モデルの複雑さを抑え、未知のデータに対しても安定した予測をしやすくする。

Ridge回帰は、1970年、アーサー・ホエルとロバート・ケナードによって提案された正則化回帰。多重共線性によって回帰係数が不安定になる問題への対策として発展した。

Lasso回帰は、1996年、ロバート・ティブシラニによって提案された正則化回帰。係数をゼロにできるため、特徴量選択にも利用できる。

それぞれの名前の由来については、もっともらしいエピソードが語られることが多いが、当時の一次資料に基づいて明確に裏付けられているとは言い難い様子。

Ridgeは、「多重共線性があるデータで回帰係数を求めると、解の候補が山の“尾根(ridge)”のように細長く伸びてしまい、その尾根に沿って解を探索することで問題を解決したことから名付けられた」としばしば説明される。

しかし実際には、ホエルは1970年のリッジ回帰の10年以上前、1959年に「リッジ分析(Ridge Analysis)」という別の目的の手法(応答曲面上で最大・最小の応答を求める手法)をすでに考案しており、その名称を後年に多重共線性対策の手法へ転用したというのが実情に近い。

「尾根状の等高線に由来する」という名前の起源自体はまだしも、「多重共線性問題を尾根伝いに解決したから名付けられた」という因果関係については、後から分かりやすく再構成された説明である可能性がある。

Lassoは、「Least Absolute Shrinkage and Selection Operatorの頭字語であると同時に、カウボーイの投げ縄(lasso)にかけた洒落でもある」としばしば説明される。

頭字語であること自体はティブシラニ自身の原論文で明示されているが、投げ縄を意図したという点について、本人が明言した一次資料は確認できていない。

「係数を“縛って”ゼロに絞り込む」というイメージと相性の良い名前であることから広く定着した説明と考えられるが、これも後年の脚色である可能性は否定できない。

手法 ペナルティの与え方（正則化） 特徴とメリット
Ridge回帰 係数の2乗和（L2正則化）をペナルティにする。 係数全体をゼロに近づけることで、係数の極端な増大を抑える。係数を完全にゼロにはしないため、変数を残したまま多重共線性による不安定さを抑えやすい。
Lasso回帰 係数の絶対値和（L1正則化）をペナルティにする。 一部の係数を完全にゼロにできるため、特徴量選択にも利用できる。

2010年代の変化

2010年代、画像認識や音声・言語処理の分野では、ディープラーニングによる革新的な成果が次々と生まれた。同じ頃、構造化データ（表形式データ）の世界でも、機械学習の実用性を大きく高める技術が発展していた。

スマートフォンの普及などに伴い、一般企業が扱うログデータや顧客データも増加していた。いわゆる「ビッグデータ」の時代。しかし、増え続けるデータを前に、現場の実務家たちはさまざまな課題に直面していた。

Random Forestは、多数の決定木を独立に学習するため並列化しやすい一方、木の本数や深さを増やすと、学習時間やモデルサイズが大きくなりやすい。

GBDTは、前までの木の予測誤差をもとに次の木を順番に追加していくため、木同士の学習を完全には並列化できないという課題があった。

こうした中で、GBDTをより高速かつ大規模なデータに適用するためのさまざまな工夫が登場する。

XGBoost

2014年、チェン・ティエンチ（Tianqi Chen 陳天奇）が公開。

計算の効率化や疎なデータへの対応、正則化など、GBDTを実用的な大規模データ分析で利用するためのさまざまな工夫を取り入れた。

機械学習コンペティションなどでも広く利用され、GBDTの代表的な実装として急速に普及した。

LightGBM

2016年、Microsoftが公開。2017年に論文発表。

特に大規模なデータを高速に処理することを重視。従来のGBDT実装に対して、木の成長方法やデータ・特徴量の扱い方に工夫を加えることで、学習時間やメモリ使用量の削減を図った。

一般的なパソコンでも大規模データを比較的短時間で扱えることから、広く普及していった。

CatBoost

2017年、ロシアの検索大手Yandexが公開。

特にカテゴリ変数を含むデータを扱いやすくすることを重視。

カテゴリ変数を専用の方法で処理し、統計量を利用する際にtarget leakageが起こることを抑える仕組みを取り入れている。

決定木からその後の手法へ

決定木は、単独では過学習しやすいという弱点を持っていた。

しかし、

決定木を組み合わせるバギング
↓
Random Forest

決定木を順番に組み合わせるブースティング
↓
GBDT
↓
XGBoost, LightGBM, CatBoost

というように、複数のモデルを組み合わせたり、計算方法を工夫したりすることで、その弱点は大きく克服されていった。

現在でも、XGBoost, LightGBM, CatBoost, Random Forestなどは構造化データを扱う機械学習で広く利用されている。

手法 特徴
ロジスティック回帰 シンプルで解釈しやすく、ベースラインとして利用しやすい。
Random Forest 複数の決定木を独立に学習し、安定した予測を得やすい。
XGBoost GBDTにさまざまな最適化を加えた、汎用性・安定性が高い実装。幅広いデータで使いやすい。
LightGBM 高速な学習と省メモリ化を重視したGBDT実装。大規模データを扱いやすい。
CatBoost カテゴリ変数を扱いやすくすることに重点を置いたGBDT実装。カテゴリ変数を含むデータで扱いやすい。過学習を抑える工夫もあり、初期設定でも比較的安定しやすい。

ただし、どの手法が常に最も優れているというわけではない。データの性質やデータ量、目的、計算資源などに応じて手法を選び、実際のデータで性能を比較することが重要になる。