論文の概要: Using dynamical quantization to perform split attempts in online tree
regressors
- arxiv url: http://arxiv.org/abs/2012.00083v2
- Date: Thu, 3 Dec 2020 13:13:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-06 14:39:47.349236
- Title: Using dynamical quantization to perform split attempts in online tree
regressors
- Title（参考訳）: 動的量子化を用いたオンラインツリー回帰器の分割試行
- Authors: Saulo Martiello Mastelini, Andre Carlos Ponce de Leon Ferreira de
Carvalho
- Abstract要約: 本稿では,オンラインツリー回帰器の数値的特徴における分割点候補の監視と評価を行うハッシュベースのアルゴリズムである量子化オブザーバ(QO)を紹介する。
QOはHoeffding Treesのようなインクリメンタルな決定木に簡単に統合でき、インスタンス毎に$O(1)$の監視コストと、分割候補を評価するためのサブ線形コストがある。
- 参考スコア（独自算出の注目度）: 0.4061135251278187
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A central aspect of online decision tree solutions is evaluating the incoming
data and enabling model growth. For such, trees much deal with different kinds
of input features and partition them to learn from the data. Numerical features
are no exception, and they pose additional challenges compared to other kinds
of features, as there is no trivial strategy to choose the best point to make a
split decision. The problem is even more challenging in regression tasks
because both the features and the target are continuous. Typical online
solutions evaluate and store all the points monitored between split attempts,
which goes against the constraints posed in real-time applications. In this
paper, we introduce the Quantization Observer (QO), a simple yet effective
hashing-based algorithm to monitor and evaluate split point candidates in
numerical features for online tree regressors. QO can be easily integrated into
incremental decision trees, such as Hoeffding Trees, and it has a monitoring
cost of $O(1)$ per instance and sub-linear cost to evaluate split candidates.
Previous solutions had a $O(\log n)$ cost per insertion (in the best case) and
a linear cost to evaluate split points. Our extensive experimental setup
highlights QO's effectiveness in providing accurate split point suggestions
while spending much less memory and processing time than its competitors.
- Abstract（参考訳）: オンライン決定ツリーソリューションの中心的な側面は、入ってくるデータを評価し、モデルの成長を可能にすることである。
そのため、ツリーはさまざまな種類の入力機能に対処し、データから学ぶために分割する。
数値的な特徴は例外ではなく、分割決定を行う最良のポイントを選択するための簡単な戦略がないため、他の種類の特徴と比較して、さらなる課題を引き起こす。
この問題は、機能とターゲットの両方が連続しているため、回帰タスクにおいてさらに難しい。
典型的なオンラインソリューションは、リアルタイムアプリケーションで生じる制約に反する分割試行で監視されるすべてのポイントを評価し、保存する。
本稿では,オンラインツリー回帰器の数値的特徴における分割点候補の監視と評価を行う,単純かつ効果的なハッシュベースアルゴリズムである量子化オブザーバ(QO)を提案する。
QOはHoeffding Treesのようなインクリメンタルな決定木に簡単に統合でき、インスタンス毎に$O(1)$の監視コストと、分割候補を評価するためのサブ線形コストがある。
以前のソリューションは挿入あたり$O(\log n)$コスト(最良の場合)と分割点を評価する線形コスト(英語版)を備えていた。
実験では,qoの有効性を強調するとともに,メモリ使用時間と処理時間を大幅に削減した。
関連論文リスト
- Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
本稿では,各データインスタンスのリソースを動的に割り当てることで,推論を高速化するスイッチブルな決定を提案する。
提案手法は, 同一の精度を維持しながら, 推論時のコスト低減に有効である。
論文 参考訳（メタデータ） (2024-05-07T17:44:54Z) - Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
教師付き学習タスクに最適な決定木を見つけることは、大規模に解決する上で難しい問題である。
近年、マルコフ決定問題 (MDP) としてこの問題の枠組みを定め、深層強化学習を用いてスケーリングに取り組むことが提案されている。
そこで我々は,全ての状態に対して生成する情報理論テスト生成関数を用いて,MDPの分解能を拡大する手法を提案する。
論文 参考訳（メタデータ） (2023-09-22T08:18:08Z) - Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting [5.199570417938866]
問題となるのがリニアプログラム(ILP)である場合について検討する。
結果のスキームが最近導入されたヤコビ自由バックプロパゲーション(JFB)と互換性があることを証明する。
提案手法は, 最短経路問題とクナップサック問題という2つの代表的なICPに対する実験により, 前方パス上のこの組み合わせDYS, 後方パス上のJFBが, 既存のスキームよりも高次元問題に対してより効果的にスケールするスキームを示す。
論文 参考訳（メタデータ） (2023-01-31T04:03:28Z) - Distributional Adaptive Soft Regression Trees [0.0]
本稿では,多変量ソフトスプリットルールを用いた分布回帰木の新しいタイプを提案する。
ソフトスプリットの大きな利点の1つは、滑らかな高次元函数を1つの木で見積もることができることである。
シミュレーションにより,アルゴリズムは優れた特性を有し,様々なベンチマーク手法より優れていることを示す。
論文 参考訳（メタデータ） (2022-10-19T08:59:02Z) - Lookback for Learning to Branch [77.32867454769936]
Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。
近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
論文 参考訳（メタデータ） (2022-06-30T02:33:32Z) - An Experimental Design Perspective on Model-Based Reinforcement Learning [73.37942845983417]
環境からの状態遷移を観察するのは費用がかかる。
標準RLアルゴリズムは通常、学習するために多くの観測を必要とする。
本稿では,マルコフ決定過程について,状態-作用対がどの程度の情報を提供するかを定量化する獲得関数を提案する。
論文 参考訳（メタデータ） (2021-12-09T23:13:57Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳（メタデータ） (2021-07-27T08:48:01Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Uncovering Feature Interdependencies in High-Noise Environments with
Stepwise Lookahead Decision Forests [0.0]
ランダムフォレストアルゴリズムの「Stepwise lookahead」変異は、二項特徴相互依存性をよりよく発見する能力を示す。
銅先物取引の長期的戦略は、毎日の物価リターンの兆候を予測するために、欲望と無作為な森林の両方を訓練することで実証される。
論文 参考訳（メタデータ） (2020-09-30T11:31:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。