論文の概要: Quality Control Algorithms for Pattern Counting
- arxiv url: http://arxiv.org/abs/2608.03439v1
- Date: Tue, 04 Aug 2026 10:35:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-05 15:30:23.140612
- Title: Quality Control Algorithms for Pattern Counting
- Title（参考訳）: パターンカウントのための品質制御アルゴリズム
- Abstract要約: 経験的アルゴリズムは品質制御問題の定義において非対称性を利用していない。
品質制御の定義における非対称性を利用して、これらの問題を解くためにpoly$(k)$時間で実行されるアルゴリズムを与えることを示す。
- 参考スコア（独自算出の注目度）: 17.340766930817335
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Formally, their goal is to accept typical inputs from the specified distribution while rejecting every input whose value of a specified statistic is far from the distributional baseline. This captures the empirical practice of using specified statistics as a proxy for the quality of randomness. Empirical algorithms, however, have not exploited the asymmetry in the definition of quality control problems, which require soundness guarantees in the worst-case while only seeking average-case completeness. Their work abstracted a problem definition emphasizing this asymmetry and used it to give efficient quality control algorithms for assessing the randomness of graphs. In this work, we introduce and study quality control problems over sequences, where the goal is to distinguish a sequence of i.i.d. characters from sequences where some specified pattern appears too often (or too infrequently) as a subsequence. We consider this problem in both the finite-alphabet setting and for real-valued sequences. We refer to the former setting as the pattern counting problem. In the latter case, the natural notion of a pattern is to consider the relative ordering of the characters in the subsequence, and we refer to this as the permutation pattern counting problem. Algorithms to approximately count (permutation) patterns of length $k$ in a worst-case sequence of length $n$ can provably require exponential in $k$ queries into the sequence. In contrast, we show that by taking advantage of the asymmetry in the definition of quality control, we give algorithms that run in poly$(k)$ time to solve these problems. We also prove that any quality control algorithm (over some natural distributions) requires superlinear queries in $k$.
- Abstract（参考訳）: 最近の研究で、Marcussen、Rubinfeld、Sudanは、与えられた入力が真にランダムであるかどうかを決定するタスクを捉えることを目的として品質制御問題の概念を導入した。
彼らのゴールは、指定された統計値の値が分布ベースラインから遠く離れた全ての入力を拒絶しながら、指定された分布からの典型的な入力を受け入れることである。
これは、ランダム性の品質のプロキシとして特定の統計を使用する経験的プラクティスをキャプチャする。
しかし、経験的アルゴリズムは、平均的な完全性のみを求めながら最悪の場合における音質保証を必要とする品質制御問題の定義において、非対称性を活用していない。
彼らの研究は、この非対称性を強調する問題定義を抽象化し、グラフのランダム性を評価するための効率的な品質制御アルゴリズムを提供するために使用した。
そこで本研究では,ある特定のパターンが頻繁に現れる(あるいは頻度が低すぎる)シーケンスから,I.d.文字のシーケンスを区別することを目的として,シーケンス上の品質制御問題を紹介し,研究する。
有限アルファベット設定と実数値列の両方においてこの問題を考える。
我々は、前者の設定をパターンカウント問題と呼ぶ。
後者の場合、パターンの自然な概念は、サブシーケンス中の文字の相対順序を考えることであり、これを置換パターンカウント問題と呼ぶ。
長さ$k$のパターンを長さ$n$の最悪のケース列で概算するアルゴリズムは、列に$k$のクエリを指数関数的に要求することができる。
対照的に、品質制御の定義における非対称性を生かして、これらの問題を解くためにpoly$(k)$時間で実行されるアルゴリズムを与える。
また、任意の品質制御アルゴリズム(いくつかの自然分布上)が$k$の超線形クエリを必要とすることも証明した。
関連論文リスト
- The Invisible Lottery: How Subtle Cues Steer Algorithm Choice in LLM Code Generation [0.6564588068252765]
タスク仕様外の文脈語やメタデータを意味するインシデントプロンプトキューは、モデルが選択したアルゴリズムを操縦することができる。
我々は、アルゴリズムのステアリングを、アルゴリズム-ファミリー分布のキュー誘起シフトとして定義する。
直接アルゴリズムの命名は、私たちがテストした最も信頼性の高い緩和です。
論文 参考訳（メタデータ） (2026-06-02T11:17:28Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。
当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Adversarially Robust Distributed Count Tracking via Partial Differential
Privacy [17.43748116766233]
分散機能監視(distributed functional monitoring)とも呼ばれる分散追跡モデルについて検討する。
このモデルは、各アイテムのストリームを受け取り、中央サーバと通信する、$k$のサイトを含む。
カウントトラッキングでは、決定論的アルゴリズムとランダム化アルゴリズムの通信に$sqrtk$ギャップがあることが知られている。
論文 参考訳（メタデータ） (2023-11-01T07:42:13Z) - On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。
A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2023-08-23T08:38:53Z) - On the Existence of a Complexity in Fixed Budget Bandit Identification [0.0]
固定予算帯域識別では、アルゴリズムは複数の分布から与えられた最終時点までのサンプルを逐次観察する。
我々は,ベルヌーイの腕を2つの腕で識別するなど,いくつかの固定予算識別タスクにおいて,そのような複雑さは存在しないことを示した。
論文 参考訳（メタデータ） (2023-03-16T16:39:00Z) - A Non-monotonic Self-terminating Language Model [62.93465126911921]
本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。
まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。
次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
論文 参考訳（メタデータ） (2022-10-03T00:28:44Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Online Sign Identification: Minimization of the Number of Errors in
Thresholding Bandits [27.09804256642197]
我々はFrank-Wolfeアルゴリズムにインスパイアされたアルゴリズム群を紹介する。
我々は幅広い問題に対して新しい明示的アルゴリズムを構築した。
我々はこの現象を洞察に富んだおもちゃの問題で説明する。
論文 参考訳（メタデータ） (2021-10-18T09:36:36Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Consistency of a Recurrent Language Model With Respect to Incomplete
Decoding [67.54760086239514]
逐次言語モデルから無限長のシーケンスを受信する問題について検討する。
不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
論文 参考訳（メタデータ） (2020-02-06T19:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。