論文の概要: Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Training

• arxiv url: http://arxiv.org/abs/2211.15368v2
• Date: Sun, 4 Jun 2023 19:01:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-07 03:55:48.367393
• Title: Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Training
• Title（参考訳）: 機械学習学習のための任意大ランダム満足度式
• Authors: Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou
• Abstract要約: 決定問題を解くことなく、任意の大きさのランダムな式を正しくラベル付けする方法を示す。 我々は1万変数の式で満足度を予測するタスクのために、既存の最先端モデルを訓練する。 同じデータセットで99%をランダムに推測するのに勝るものは見当たらない。
• 参考スコア（独自算出の注目度）: 5.414308305392762
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Applying deep learning to solve real-life instances of hard combinatorial problems has tremendous potential. Research in this direction has focused on the Boolean satisfiability (SAT) problem, both because of its theoretical centrality and practical importance. A major roadblock faced, though, is that training sets are restricted to random formulas of size several orders of magnitude smaller than formulas of practical interest, raising serious concerns about generalization. This is because labeling random formulas of increasing size rapidly becomes intractable. By exploiting the probabilistic method in a fundamental way, we remove this roadblock entirely: we show how to generate correctly labeled random formulas of any desired size, without having to solve the underlying decision problem. Moreover, the difficulty of the classification task for the formulas produced by our generator is tunable by varying a simple scalar parameter. This opens up an entirely new level of sophistication for the machine learning methods that can be brought to bear on Satisfiability. Using our generator, we train existing state-of-the-art models for the task of predicting satisfiability on formulas with 10,000 variables. We find that they do no better than random guessing. As a first indication of what can be achieved with the new generator, we present a novel classifier that performs significantly better than random guessing 99% on the same datasets, for most difficulty levels. Crucially, unlike past approaches that learn based on syntactic features of a formula, our classifier performs its learning on a short prefix of a solver's computation, an approach that we expect to be of independent interest.
• Abstract（参考訳）: 複雑な組み合わせ問題の実例をディープラーニングで解決することは、大きな可能性を秘めている。 この方向の研究は、理論的な中心性と実践的重要性の両方から、ブール満足度(SAT)問題に焦点を当てている。 しかし、大きな障害の1つは、トレーニングセットが実用上の関心のある公式よりも数桁小さい大きさのランダムな公式に制限され、一般化に関する深刻な懸念が高まることである。 これは、増大する大きさのランダムな公式のラベル付けが急速に難解になるためである。 確率的手法を基本的手法で活用することにより、このブロックを完全に除去する: 根底にある決定問題を解くことなく、任意の大きさのランダムな公式を正しくラベル付けする方法を示す。 さらに, 単純なスカラーパラメータを変化させることで, 生成元が生成する公式の分類作業の難しさを調整できる。 これにより、Satifiability(満足度)に対処できる機械学習手法の、まったく新しいレベルの洗練がもたらされる。 生成器を使って既存の最先端モデルを訓練し、1万変数の式で満足度を予測する。 彼らはランダムな推測以上のことはしない。 新しいジェネレータによって何が達成できるかの最初の兆候として、多くの難易度において、同じデータセットで99%をランダムに推測するよりも大幅に優れた新しい分類器を提案する。 重要な点は、式を構文的に特徴付けして学習する過去のアプローチと異なり、我々の分類器は、解答者の計算の短い接頭辞でその学習を実行する。

関連論文リスト

• A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic [4.7223923266180785]
  整数値の確率変数に対する線形算術をテンソル演算として定式化する。 我々は、自由な勾配に基づく学習のために、事実上アンロック可能な、微分可能なデータ構造を得る。
  論文  参考訳（メタデータ） (2024-10-16T09:16:10Z)
• Deep Linear Probe Generators for Weight Space Learning [39.90685550999956]
  プローブは、学習した入力(プローブ)のセットをモデルに渡すことでモデルを表し、対応する出力の上に予測器を訓練する。 ProbeGenは、深い線形アーキテクチャを備えた共有ジェネレータモジュールを追加し、構造化プローブに対する誘導バイアスを提供する。 ProbeGenは最先端よりも大幅にパフォーマンスが良く、非常に効率的で、他のトップアプローチの30～1000倍のFLOPを必要とする。
  論文  参考訳（メタデータ） (2024-10-14T17:59:41Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  本稿では,様々な高次元リッジ回帰モデルの訓練および一般化性能の簡潔な導出について述べる。 本稿では,物理と深層学習の背景を持つ読者を対象に,これらのトピックに関する最近の研究成果の紹介とレビューを行う。
  論文  参考訳（メタデータ） (2024-05-01T15:59:00Z)
• Probabilistic Invariant Learning with Randomized Linear Classifiers [24.485477981244593]
  表現的かつ不変だがリソースが少ないランダム性と設計モデルをどのように活用するかを示す。 ランダム化アルゴリズムに着想を得て,Randomized Linears (RLC) と呼ばれる二進分類モデルを提案する。
  論文  参考訳（メタデータ） (2023-08-08T17:18:04Z)
• Rough Randomness and its Application [0.0]
  本研究の目的は、さまざまな粗いプロセスを捕捉し、関連するモデルを構築し、他の機械学習アルゴリズムの有効性を探ることである。 大心的推論と呼ばれる乱数関数のクラスは、これらに中心的な役割を果たす。
  論文  参考訳（メタデータ） (2023-03-21T12:22:33Z)
• A Note on High-Probability versus In-Expectation Guarantees of Generalization Bounds in Machine Learning [95.48744259567837]
  統計的機械学習理論は、しばしば機械学習モデルの一般化を保証するよう試みる。 機械学習モデルのパフォーマンスに関する声明は、サンプリングプロセスを考慮する必要がある。 1つのステートメントを別のステートメントに変換する方法を示します。
  論文  参考訳（メタデータ） (2020-10-06T09:41:35Z)
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters [10.279748604797911]
  機械学習とデータサイエンスの主な問題は、最適化問題として日常的にモデル化され、最適化アルゴリズムによって解決される。 データ量の増加と、これらの不条件最適化タスクを定式化するために使用される統計モデルのサイズと複雑さにより、これらの課題に対処できる新しい効率的なアルゴリズムが必要である。 この論文では,これらの課題をそれぞれ異なる方法で処理する。ビッグデータ問題に効率的に対処するために,各イテレーションでトレーニングデータの小さなランダムサブセットのみを検査する新しい手法を開発する。 大きなモデル問題に対処するために、イテレーション毎に更新されるメソッドを開発します。
  論文  参考訳（メタデータ） (2020-08-26T21:15:18Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• Continual Learning using a Bayesian Nonparametric Dictionary of Weight Factors [75.58555462743585]
  訓練されたニューラルネットワークは、シーケンシャルなタスク設定で破滅的な忘れを経験する傾向がある。 Indian Buffet Process (IBP) に基づく原則的非パラメトリック手法を提案する。 連続学習ベンチマークにおける本手法の有効性を実証し、トレーニングを通して重み要因の配分と再利用方法を分析する。
  論文  参考訳（メタデータ） (2020-04-21T15:20:19Z)
• The data-driven physical-based equations discovery using evolutionary approach [77.34726150561087]
  与えられた観測データから数学的方程式を発見するアルゴリズムについて述べる。 このアルゴリズムは遺伝的プログラミングとスパース回帰を組み合わせたものである。 解析方程式の発見や偏微分方程式(PDE)の発見にも用いられる。
  論文  参考訳（メタデータ） (2020-04-03T17:21:57Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。