論文の概要: Theory and Algorithms for Shapelet-based Multiple-Instance Learning
- arxiv url: http://arxiv.org/abs/2006.01130v3
- Date: Tue, 13 Oct 2020 06:57:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 12:33:23.482588
- Title: Theory and Algorithms for Shapelet-based Multiple-Instance Learning
- Title（参考訳）: shapelet-based multi-instance learningの理論とアルゴリズム
- Authors: Daiki Suehiro, Kohei Hatano, Eiji Takimoto, Shuji Yamamoto, Kenichi
Bannai, Akiko Takeda
- Abstract要約: 本稿では,データ単位がバッグと呼ばれるインスタンスから構成されるMultiple-Instance Learning(MIL)の新たな定式化を提案する。
目標は、"shapelet"(またはパターン)との類似性に基づいて、バッグの優れた分類器を見つけることである。
私たちの定式化では、すべての可能なので、したがって無限に多くのシェイプレットを使い、よりリッチな分類器のクラスを生み出す。
- 参考スコア（独自算出の注目度）: 5.08418565337126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new formulation of Multiple-Instance Learning (MIL), in which a
unit of data consists of a set of instances called a bag. The goal is to find a
good classifier of bags based on the similarity with a "shapelet" (or pattern),
where the similarity of a bag with a shapelet is the maximum similarity of
instances in the bag. In previous work, some of the training instances are
chosen as shapelets with no theoretical justification. In our formulation, we
use all possible, and thus infinitely many shapelets, resulting in a richer
class of classifiers. We show that the formulation is tractable, that is, it
can be reduced through Linear Programming Boosting (LPBoost) to Difference of
Convex (DC) programs of finite (actually polynomial) size. Our theoretical
result also gives justification to the heuristics of some of the previous work.
The time complexity of the proposed algorithm highly depends on the size of the
set of all instances in the training sample. To apply to the data containing a
large number of instances, we also propose a heuristic option of the algorithm
without the loss of the theoretical guarantee. Our empirical study demonstrates
that our algorithm uniformly works for Shapelet Learning tasks on time-series
classification and various MIL tasks with comparable accuracy to the existing
methods. Moreover, we show that the proposed heuristics allow us to achieve the
result with reasonable computational time.
- Abstract（参考訳）: 本稿では,データ単位がバッグと呼ばれる一連のインスタンスから構成されるMultiple-Instance Learning(MIL)の新たな定式化を提案する。
その目的は、形をしたバッグの類似度がバッグ内のインスタンスの最大類似度である"shapelet"(あるいはパターン)との類似度に基づいて、バッグの適切な分類方法を見つけることである。
以前の研究では、いくつかのトレーニングインスタンスは理論的正当性のないシェープレットとして選択されている。
私たちの定式化では、すべての可能なので、したがって無限に多くのシェイプレットを使い、よりリッチな分類器のクラスを生み出す。
定式化は、Linear Programming Boosting (LPBoost) によって有限(実際に多項式)サイズのConvex (DC) プログラムの差分に還元可能であることを示す。
我々の理論的な結果はまた、以前の作品のヒューリスティックスを正当化する。
提案アルゴリズムの時間的複雑さは、トレーニングサンプルのすべてのインスタンスの集合の大きさに大きく依存する。
多数のインスタンスを含むデータに適用するために、理論的な保証を失うことなくアルゴリズムのヒューリスティックな選択肢を提案する。
実験により,本アルゴリズムは時系列分類におけるシェープレット学習タスクと,既存の手法に匹敵する精度で様々なMILタスクに一様に作用することを示した。
さらに,提案するヒューリスティクスにより,合理的な計算時間で結果が得られることを示す。
関連論文リスト
- Derandomizing Multi-Distribution Learning [28.514129340758938]
マルチディストリビューション学習では、複数のデータ分散でうまく動作する単一の予測子を学習する。
近年の研究では、オラクル効率のアルゴリズムにより、ほぼ最適サンプルの複雑さが達成されている。
これらのアルゴリズムは、複数の分布に対する決定論的予測子を生成するためにデランドマイズできるのだろうか?
論文 参考訳（メタデータ） (2024-09-26T06:28:56Z) - A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。
アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
論文 参考訳（メタデータ） (2024-06-20T21:24:47Z) - FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。
既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。
本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
論文 参考訳（メタデータ） (2024-06-06T04:05:54Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳（メタデータ） (2024-02-16T04:32:22Z) - PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses [18.944561572423726]
我々は、事象レベルの損失関数のための集約セット(文献ではバッグと呼ばれる)の構築に焦点をあてる。
より均一なサンプルの袋を適応的に形成するPreferBoostアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-07T16:06:20Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Provably Efficient Representation Learning with Tractable Planning in
Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究
まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。
次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文 参考訳（メタデータ） (2023-06-21T16:04:03Z) - Flow Network based Generative Models for Non-Iterative Diverse Candidate
Generation [110.09855163856326]
本稿では,アクションのシーケンスからオブジェクトを生成するためのポリシーを学習する問題について述べる。
本稿では,生成過程をフローネットワークとして見たGFlowNetを提案する。
提案した目的の任意のグローバルな最小限が、所望の分布から標本化する方針を導出することを証明する。
論文 参考訳（メタデータ） (2021-06-08T14:21:10Z) - An Empirical Comparison of Instance Attribution Methods for NLP [62.63504976810927]
本研究は,トレーニングサンプルの重要性に関して,異なるインスタンス属性が一致した度合いを評価する。
単純な検索メソッドは、グラデーションベースの方法によって識別されたものと異なるトレーニングインスタンスを生成する。
論文 参考訳（メタデータ） (2021-04-09T01:03:17Z) - Clustering with Penalty for Joint Occurrence of Objects: Computational
Aspects [0.0]
Hol'y, Sokol および vCern'y クラスタ・オブジェクトのメソッドは、与えられた多くの集合におけるそれらの出現率に基づいている。
この考え方は、同じクラスタ内の同じクラスタから複数のオブジェクトが発生することを最小限にすることを目的としている。
本稿では,本手法の計算的側面について考察する。
論文 参考訳（メタデータ） (2021-02-02T10:39:27Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。