論文の概要: Scalable Rule Lists Learning with Sampling
- arxiv url: http://arxiv.org/abs/2406.12803v1
- Date: Tue, 18 Jun 2024 17:15:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-19 17:49:20.188808
- Title: Scalable Rule Lists Learning with Sampling
- Title(参考訳): サンプリングで学ぶスケーラブルなルールリスト
- Authors: Leonardo Pellegrina, Fabio Vandin,
- Abstract要約: 大規模データセットからほぼ最適なルールリストを学習するための新しいアプローチを提案する。
本アルゴリズムは,最適規則リストの近似を効率的に取得するためにサンプリングを用いる。
我々のアルゴリズムは、最先端の正確なアプローチに対して最大2桁の速度で、ほぼ最適なルールリストを識別する。
- 参考スコア(独自算出の注目度): 9.681286056736292
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are among the best-known and easily interpretable ones. However, finding optimal rule lists is computationally challenging, and current approaches are impractical for large datasets. We present a novel and scalable approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list with rigorous guarantees on the quality of the approximation. In particular, our algorithm guarantees to find a rule list with accuracy very close to the optimal rule list when a rule list with high accuracy exists. Our algorithm builds on the VC-dimension of rule lists, for which we prove novel upper and lower bounds. Our experimental evaluation on large datasets shows that our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches. Moreover, our algorithm is as fast as, and sometimes faster than, recent heuristic approaches, while reporting higher quality rule lists. In addition, the rules reported by our algorithm are more similar to the rules in the optimal rule list than the rules from heuristic approaches.
- Abstract(参考訳): 解釈可能なモデルを学ぶことは、社会的に重要な意思決定における機械学習の優位性の高まりを考えると、機械学習研究の大きな焦点となっている。
解釈可能なモデルの中で、ルールリストは最もよく知られ、容易に解釈できるモデルの一つである。
しかし、最適なルールリストを見つけることは計算的に困難であり、現在のアプローチは大規模なデータセットでは実用的ではない。
大規模データセットからほぼ最適なルールリストを学習するための,新しい,スケーラブルなアプローチを提案する。
提案アルゴリズムはサンプリングを用いて最適規則リストの近似を効率よく取得し,近似の精度を厳格に保証する。
特に,高精度なルールリストが存在する場合に,最適なルールリストに非常に近い精度のルールリストを見つけることを保証している。
我々のアルゴリズムは、新しい上限と下限を証明した規則リストのVC次元に基づいている。
大規模データセットに対する実験により,我々のアルゴリズムは,最先端の厳密なアプローチに対して,最大2桁の速度で,ほぼ最適なルールリストを同定することを示した。
さらに、我々のアルゴリズムは、最近のヒューリスティックなアプローチと同じくらい高速であり、時には高速であると同時に、より高い品質のルールリストを報告している。
さらに,本アルゴリズムにより報告された規則は,ヒューリスティックな手法による規則よりも,最適規則リストの規則に類似している。
関連論文リスト
- Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-11T07:28:35Z) - Efficient learning of large sets of locally optimal classification rules [0.0]
従来のルール学習アルゴリズムは、単純なルールの集合を見つけることを目的としており、各ルールは可能な限り多くの例をカバーする。
本稿では、この方法で発見されたルールは、それらがカバーする例のそれぞれに対して最適な説明ではないかもしれないと論じる。
本稿では,1つの特殊化ループと1つの一般化ループからなるグリーディ最適化において,各トレーニング例をカバーする最良のルールを見つけることを目的とした,効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-24T11:40:28Z) - Bayes Point Rule Set Learning [5.065947993017157]
解釈可能性は、機械学習アルゴリズムの設計においてますます重要な役割を担っている。
可分正規形式は、規則の集合を表現する最も解釈可能な方法である。
本稿では、DNF型ルールセットを学習するために、FIND-Sアルゴリズムの効果的なボトムアップ拡張を提案する。
論文 参考訳(メタデータ) (2022-04-11T16:50:41Z) - US-Rule: Discovering Utility-driven Sequential Rules [52.68017415747925]
我々は,高ユーティリティシーケンシャルルールを効率的にマイニングする,US-Ruleと呼ばれる高速アルゴリズムを提案する。
より厳密な上界(LEEU, REEU, LERSU, RERSU)とそれに対応する刈り取り戦略を提案する。
US-Ruleは実行時間、メモリ消費、スケーラビリティの点でパフォーマンスが向上する。
論文 参考訳(メタデータ) (2021-11-29T23:38:28Z) - Interpretable and Fair Boolean Rule Sets via Column Generation [18.08486863429421]
整数プログラムは、規則単純性のために最適に分類精度を交換するように定式化される。
公平性の設定を考慮し、分類パリティの2つの異なる尺度に関する明示的な制約を含むように定式化を拡張した。
他の公正かつ解釈可能な分類器と比較して、我々の手法は、公正性のより厳密な概念に適合する規則セットを精度の低いトレードオフで見つけることができる。
論文 参考訳(メタデータ) (2021-11-16T13:40:28Z) - LPRules: Rule Induction in Knowledge Graphs Using Linear Programming [4.94950858749529]
ルールベースのメソッドは、入力グラフ内の既存の事実をキャプチャする一階述語論理ルールを学び、これらのルールを使用して、行方不明の事実を推論する。
このような方法の大きな欠点は、大規模なデータセットに対するスケーラビリティの欠如である。
候補ルールのリストからルールを選択し、重み付けを割り当てるための単純な線形プログラミング(LP)モデルを提案する。
論文 参考訳(メタデータ) (2021-10-15T17:58:16Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Better Short than Greedy: Interpretable Models through Optimal Rule
Boosting [10.938624307941197]
ルールアンサンブルは、予測精度とモデル解釈可能性の間の有用なトレードオフを提供するように設計されている。
与えられたアンサンブルサイズに対して最大予測力の規則アンサンブルを適合させる新しい手法を提案する。
論文 参考訳(メタデータ) (2021-01-21T01:03:48Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳(メタデータ) (2020-07-06T15:20:17Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。