論文の概要: Heuristic Algorithms for the Approximation of Mutual Coherence
- arxiv url: http://arxiv.org/abs/2307.01639v1
- Date: Tue, 4 Jul 2023 10:47:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-06 17:30:19.001420
- Title: Heuristic Algorithms for the Approximation of Mutual Coherence
- Title(参考訳): 相互コヒーレンス近似のためのヒューリスティックアルゴリズム
- Authors: Gregor Betz, Vera Chekan, Tamara Mchedlidze
- Abstract要約: ドイツでは、この制度は有権者が政治的嗜好に最も近い候補者を見つけるのに役立つ。
相互一貫性の正確な反復は、意見のすべての部分集合に対する反復のために非常に時間がかかります。
この研究は、この計算を加速する最初の研究である。
精度はWale-O-Matのようなシステムで使用するのに十分正確である。
- 参考スコア(独自算出の注目度): 0.22099217573031676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Mutual coherence is a measure of similarity between two opinions. Although
the notion comes from philosophy, it is essential for a wide range of
technologies, e.g., the Wahl-O-Mat system. In Germany, this system helps voters
to find candidates that are the closest to their political preferences. The
exact computation of mutual coherence is highly time-consuming due to the
iteration over all subsets of an opinion. Moreover, for every subset, an
instance of the SAT model counting problem has to be solved which is known to
be a hard problem in computer science. This work is the first study to
accelerate this computation. We model the distribution of the so-called
confirmation values as a mixture of three Gaussians and present efficient
heuristics to estimate its model parameters. The mutual coherence is then
approximated with the expected value of the distribution. Some of the presented
algorithms are fully polynomial-time, others only require solving a small
number of instances of the SAT model counting problem. The average squared
error of our best algorithm lies below 0.0035 which is insignificant if the
efficiency is taken into account. Furthermore, the accuracy is precise enough
to be used in Wahl-O-Mat-like systems.
- Abstract(参考訳): 相互一貫性は2つの意見の類似性の尺度である。
この概念は哲学に由来するが、Wahl-O-Matシステムのような幅広い技術には必須である。
ドイツでは、この制度は有権者が政治的嗜好に最も近い候補者を見つけるのに役立つ。
相互コヒーレンスの正確な計算は、意見のすべての部分集合の反復のために非常に時間がかかる。
さらに、各サブセットに対して、SATモデルカウント問題(英語版)のインスタンスを解く必要があるが、これはコンピュータ科学において難しい問題である。
この研究は、この計算を加速する最初の研究である。
本稿では,いわゆる確認値の分布を3つのガウスの混合としてモデル化し,モデルパラメータを推定する効率的なヒューリスティックスを提案する。
相互コヒーレンスは、その分布の期待値と近似される。
提示されたアルゴリズムのいくつかは完全に多項式時間であり、他のアルゴリズムは少数のsatモデルカウント問題の解のみを必要とする。
我々の最善のアルゴリズムの平均二乗誤差は 0.0035 以下であり、効率を考慮すると重要ではない。
さらに、wahl-o-matライクなシステムでは精度が十分である。
関連論文リスト
- Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳(メタデータ) (2023-12-24T07:46:37Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳(メタデータ) (2023-06-07T14:07:35Z) - Efficient One Sided Kolmogorov Approximation [7.657378889055477]
本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。
これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
論文 参考訳(メタデータ) (2022-07-14T10:03:02Z) - Formalizing Preferences Over Runtime Distributions [25.899669128438322]
アルゴリズムよりも好みを記述したスコアリング関数を特徴付けるために,ユーティリティ理論のアプローチを用いる。
本稿では,不特定容量分布のモデル化における最大エントロピー手法の活用法を示す。
論文 参考訳(メタデータ) (2022-05-25T19:43:48Z) - Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文 参考訳(メタデータ) (2021-12-03T14:39:10Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文 参考訳(メタデータ) (2021-04-14T19:21:59Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳(メタデータ) (2020-11-19T10:00:54Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。