MLlib でのスケーラブルな決定木

決定木とそのアンサンブルは、分類や回帰といった機械学習タスクにおいて業界の主力製品です。 決定木は解釈が容易で、カテゴリ的および連続的特徴を扱い、マルチクラス分類に拡張でき、特徴量のスケーリングを必要とせず、非線形性と特徴量の相互作用を捉えることができます。

その人気のため、ほぼすべての機械学習ライブラリが決定木アルゴリズムの実装を提供しています。 しかし、そのほとんどは単一マシンでの計算用に設計されており、分散環境にエレガントに拡張することはめったにありません。 Apache Spark はスケーラブルな分散決定木実装に最適なプラットフォームです。これは、Spark のインメモリコンピューティングにより、トレーニングデータセットに対して複数のパスを効率的に実行できるためです。

約1年前、オープンソースの開発者たちは力を合わせて高速な分散型決定木実装を考案しました。これは、リリース 1.0 以降、Spark MLlib ライブラリの一部となっています。 それ以来、Spark コミュニティは積極的に決定木のコードを改善してきました。 このブログ記事では、実装について説明し、重要な最適化の一部を強調し、スケーラビリティを実証するテスト結果を紹介します。

Spark 1.1 の新機能: MLlib の決定木は多クラス分類をサポートするようになり、いくつかのパフォーマンス最適化が含まれています。 現在では、Scala と Java に加えて、Python 向けの API があります。

アルゴリズムの背景

大まかなレベルでは、決定木モデルは、ラベルを予測するために特徴量値をテストする階層型の if-else ステートメントと考えることができます。 以下に、二値分類タスクのモデル例を示します。 これは1970年代の自動車走行距離データに基づいています！ このシステムは、重量（重い/軽い）と馬力に基づいて車両の走行距離（高/低）を予測します。

モデルは、トレーニングデータセットから学習され、トップダウンでツリーを構築します。 if-else ステートメントは分割基準とも呼ばれますが、これは情報ゲインの概念を最大限に活用するために選択されています。つまり、親ノードと比較して、基盤となる (2 つ) の子ノードのラベルの変動性を低減します。 学習された決定木モデルは、あとで新しいインスタンスのラベルを予測するために使用できます。

これらのモデルは解釈可能であり、実際にはうまく機能することがよくあります。 また、アンサンブル・ツリー・アルゴリズムを使用して、木を組み合わせることでさらに強力なモデルを構築することもできます。 ランダムフォレストやブーストツリーなどの木のアンサンブルは、分類と回帰の両方のタスクにおいて業界でトップパフォーマンスを発揮することがよくあります。

シンプルな API

以下の例は、MLlib の決定木を、Spark 1.1 の新しい Python API を使用して数行のコードで簡単にトレーニングする方法を示しています。 このツールはデータセットを読み取り、決定木モデルをトレーニングし、モデルのトレーニングエラーを測定します。 Java と Scala の例は DecisionTree の Spark ドキュメントにあります。

最適化された実装

Spark は、洗練された DAG 実行エンジンと反復計算用のメモリ内キャッシュ機能を備えているため、スケーラブルな分散決定木実装に最適なコンピューティングプラットフォームです。 ここでは、いくつかの重要な最適化について説明します。

レベル別トレーニング: ツリーの同じレベルにあるすべてのノードの分割を同時に選択します。 このレベルごとの最適化により、データセットのパス回数が指数関数的に減少します。つまり、ツリー内の各ノードに対して 1 回のパスではなく、各レベルに対して 1 回のパスを作成します。 これにより、I/O、計算、通信のコストを大幅に削減できます。

近似分位数: 単一マシンでの実装では、通常、連続特徴量に対してソート済みの一意の特徴量値を最適な分割計算のための分割候補として使用します。 しかし、ソート済みの一意の値を見つけることは、分散データセットに対してコストのかかる操作です。 MLlib の決定ツリーは、各特徴量の分位数を分割候補として使用します。 これは、正確性を大幅に低下させることなく意思決定木のパフォーマンスを向上させるための標準的なトレードオフです。

マップ操作を避ける: 初期の決定木のプロトタイプ実装では、ツリーノードに最適な分割を選択する際にマップ操作と削減操作の両方を使用していました。 現在のコードでは、事前に計算された分割候補の既知の構造を利用してマップステップを回避することで、計算と通信の使用量が大幅に削減されています。

ビン単位計算: 最適な分割計算は特徴量をビンに離散化し、これらのビンは分割に必要な十分な統計量を計算するために使用されます。 各インスタンスのビン化された表現を事前計算することで、各反復の計算量を節約できます。

スケーラビリティ

私たちは、さまざまなデータセットとクラスターサイズに関する経験結果を使用して、MLlib の決定木のスケーラビリティを実証します。

データセットサイズに合わせた拡張

下の 2 つの図は、データセット内のインスタンス数と特徴量をスケーリングする際の決定木のトレーニング時間を表しています。 トレーニング時間は直線的に増加し、実装のスケーラビリティが強調されました。

これらのテストは、マスターノード 1 つとワーカーノード 15 つの EC2 クラスター上で実行され、r3.2xlarge インスタンス (8 つの仮想 CPU、61 GB のメモリ) を使用しました。 ツリーは 6 つのレベルにまで構築され、データセットは spark-perfライブラリによって生成されました。

Spark 1.1 による高速化

次の 2 つの図は、元の Apache Spark 1.0 実装と比較して Apache Spark 1.1 における改善点を示しています。 同じデータセットとクラスタ上で、この新しい実装は多くのデータセットで4~5倍高速です。

今後の予定は？

リリース1.1以降のツリーベースのアルゴリズムの開発は、主にランダムフォレストやブーストなどのアンサンブルアルゴリズムに焦点を当てます。 また、パフォーマンスのために意思決定ツリーコードを最適化し続け、今後のリリースでより多くのオプションをサポートする予定です。

自分で決定木の使用を開始するには、今すぐ Spark 1.1 をダウンロードしてください。

参考文献

• MLlib の決定ツリーに関するドキュメントで例と API を参照してください。
• 2014 年 Spark Summit での意思決定木のプレゼンテーションをご覧ください。
• 2014 年 9 月にサンフランシスコで Scala/ベイエリアで開催された機械学習ミートアップでの決定木に関する別の講演のビデオとスライドをご覧ください。

謝辞

Spark MLlib の決定木の作業は当初、Hirakendu Das 氏 (Yahoo Labs)、Evan Sparks 氏 (UC Berkeley AMPLab)、および Ameet Talwalkar 氏と Xiangrui Meng 氏 (Databricks) と共同で行われました。 その後も多くの貢献者が参加しており、私たちはあなたのインプットを歓迎しています！

(このブログ記事はAI翻訳ツールを使用して翻訳されています) 原文記事