論文の概要: 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タスクに一様に作用することを示した。
さらに,提案するヒューリスティクスにより,合理的な計算時間で結果が得られることを示す。
関連論文リスト
- Collaborative Learning with Different Labeling Functions [8.53926206853583]
我々は、$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) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-11-09T02:33:36Z) - Fast learning from label proportions with small bags [0.0]
ラベルパーセンテージ(LLP)から学ぶ場合、インスタンスはバッグにグループ化され、トレーニングバッグの相対クラスパーセンテージが与えられたインスタンス分類器を学習する。
本研究では,全ての一貫したラベルの組み合わせを明示的に考慮し,より効率的なアルゴリズムを設計できる小袋の事例に焦点を当てる。
論文 参考訳(メタデータ) (2021-10-07T13:11:18Z) - 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) - Meta-learning with Stochastic Linear Bandits [120.43000970418939]
我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。
我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
論文 参考訳(メタデータ) (2020-05-18T08:41:39Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳(メタデータ) (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。