Fugu-MT 論文翻訳(概要): Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle

論文の概要: Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle

arxiv url: http://arxiv.org/abs/2305.13402v1
Date: Mon, 22 May 2023 18:33:21 GMT
ステータス: 処理完了
システム内更新日: 2023-05-24 21:08:48.656439
Title: Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle
Title（参考訳）: 同じクラスタオラクルを用いた有限集合分割のエラー耐性の高い完全クエリ学習
Authors: Adela Frances DePavia, Olga Medrano Mart\'in del Campo, Erasmo Tani
Abstract要約: まず、学習分割と相関クラスタリングの新たな関連性を強調します。この接続を使って、この問題に対してR'enyi-Ulamスタイルの分析フレームワークを構築し、最悪のクエリの複雑さに対して、上位と下位の境界を証明します。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection between learning partitions and correlation clustering. Then we use this connection to build a R\'enyi-Ulam style analytical framework for this problem, and prove upper and lower bounds on its worst-case query complexity. Further, we bound the expected performance of a relevant randomized algorithm. Finally, we study the relationship between adaptivity and query complexity for this problem and related variants.
Abstract（参考訳）: 本稿では,有界対向誤差の存在下での同一クラスタオラクルへのアクセスを通じて,分割の正確な回復のためのアクティブラーニングの研究を開始する。まず,学習分割と相関クラスタリングの新たな関係を強調する。そして、この接続を使ってr\'enyi-ulamスタイルの分析フレームワークを構築し、最悪の場合のクエリの複雑さの上限を上下に証明します。さらに、関連するランダム化アルゴリズムの期待性能を制限した。最後に,この問題に対する適応性と問合せ複雑性の関係について検討する。

関連論文リスト

Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
論文参考訳（メタデータ） (2024-03-21T13:52:30Z)
Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection [0.0]
並列コンピューティング環境では、相関ベースのクラスタリングは$mathcalO(p)$サンプル複雑性低減率を達成することができる。ニューラルアーキテクチャ検索のような大規模AIアプリケーションでは、スクリーニングなしバージョンの手順が、サンプル効率の点で完全に順序づけられたベンチマークを驚くほど上回っている。
論文参考訳（メタデータ） (2024-02-03T15:56:03Z)
Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文参考訳（メタデータ） (2024-02-02T13:31:24Z)
Causal Feature Selection via Transfer Entropy [59.999594949050596]
因果発見は、観察データによる特徴間の因果関係を特定することを目的としている。本稿では,前向きと後向きの機能選択に依存する新たな因果的特徴選択手法を提案する。精度および有限サンプルの場合の回帰誤差と分類誤差について理論的に保証する。
論文参考訳（メタデータ） (2023-10-17T08:04:45Z)
Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文参考訳（メタデータ） (2023-04-14T11:35:35Z)
Correlation Clustering with Active Learning of Pairwise Similarities [3.86170450233149]
相関クラスタリングは、正と負のペアの類似性を扱う、よく知られた教師なしの学習環境である。本稿では, ペアの類似性が事前に与えられておらず, コスト効率のよいクエリを行なわなければならない場合について検討する。このタスクのための汎用的なアクティブラーニングフレームワークを開発し、いくつかの利点の恩恵を受けている。
論文参考訳（メタデータ） (2023-02-20T20:39:07Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
Contextual Model Aggregation for Fast and Robust Federated Learning in Edge Computing [88.76112371510999]
フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
論文参考訳（メタデータ） (2022-03-23T21:42:31Z)
Faster Deterministic Approximation Algorithms for Correlation Clustering and Cluster Deletion [5.584060970507507]
相関クラスタリングは、ペアの類似性と相似性スコアに基づいてデータセットをパーティショニングするフレームワークである。本稿では, 相関クラスタリング問題とエッジラベリング問題との新たな関係性を示す。我々は,決定論的定数係数近似の保証を有する相関クラスタリングのための新しい近似アルゴリズムを開発し,標準線形プログラミング緩和を回避する。
論文参考訳（メタデータ） (2021-11-20T22:47:19Z)
Learning to Cluster via Same-Cluster Queries [26.284461833343403]
我々は,同一クラスタクエリに応答可能なオラクルを用いて,データポイントのクラスタ化を学習する問題について検討する。提案する2つのアルゴリズムは, 理論的保証を証明可能とし, 合成データと実世界のデータの両方に関する広範な実験により, 有効性を検証する。
論文参考訳（メタデータ） (2021-08-17T00:37:11Z)
Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文参考訳（メタデータ） (2020-10-07T01:33:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。