論文の概要: Empirical Computation
- arxiv url: http://arxiv.org/abs/2503.10954v1
- Date: Thu, 13 Mar 2025 23:40:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-17 13:04:56.276779
- Title: Empirical Computation
- Title（参考訳）: 経験計算
- Authors: Eric Tang, Marcel Böhme,
- Abstract要約: 我々はこのアプローチを*経験的計算*と呼び、その能力と限界が古典的で合理主義的な計算フレームワークでは理解できないことを観察する。
我々の目的は、興味深い問題に満ちたSEのフィールドとして経験的計算を確立することである。
- 参考スコア（独自算出の注目度）: 14.14554547058963
- License:
- Abstract: In this vision paper, we explore the challenges and opportunities of a form of computation that employs an empirical (rather than a formal) approach, where the solution of a computational problem is returned as empirically most likely (rather than necessarily correct). We call this approach as *empirical computation* and observe that its capabilities and limits *cannot* be understood within the classic, rationalist framework of computation. While we take a very broad view of "computational problem", a classic, well-studied example is *sorting*: Given a set of $n$ numbers, return these numbers sorted in ascending order. * To run a classical, *formal computation*, we might first think about a *specific algorithm* (e.g., merge sort) before developing a *specific* program that implements it. The program will expect the input to be given in a *specific* format, type, or data structure (e.g., unsigned 32-bit integers). In software engineering, we have many approaches to analyze the correctness of such programs. From complexity theory, we know that there exists no correct program that can solve the average instance of the sorting problem faster than $O(n\log n)$. * To run an *empirical computation*, we might directly ask a large language model (LLM) to solve *any* computational problem (which can be stated informally in natural language) and provide the input in *any* format (e.g., negative numbers written as Chinese characters). There is no (problem-specific) program that could be analyzed for correctness. Also, the time it takes an LLM to return an answer is entirely *independent* of the computational complexity of the problem that is solved. What are the capabilities or limits of empirical computation in the general, in the problem-, or in the instance-specific? Our purpose is to establish empirical computation as a field in SE that is timely and rich with interesting problems.
- Abstract（参考訳）: 本稿では,経験的(形式的ではなく)アプローチを取り入れた計算形態の課題と機会を探究し,計算問題の解を経験的(必ずしも正しくない)確率で返却する。
我々はこのアプローチを*経験的計算*と呼び、その能力と限界*は古典的で合理主義的な計算フレームワークの中で理解できないことを観察する。
計算問題(computational problem)"について非常に広い視点で見ていくが、古典的でよく研究されている例は *sorting* である。
* 古典的な *形式的な計算* を実行するには、* 固有のアルゴリズム* (例えば、マージソート) を最初に考え、それを実装する * 固有の* プログラムを開発するかもしれません。
プログラムは、入力が*指定の*フォーマット、型、データ構造(例えば、符号なしの32ビット整数)で与えられることを期待する。
ソフトウェア工学では、そのようなプログラムの正確性を分析するための多くのアプローチがある。
複雑性理論から、ソート問題の平均インスタンスを$O(n\log n)$より早く解くことのできる正しいプログラムは存在しないことが分かっている。
* 経験的計算* を実行するには、大言語モデル (LLM) に直接、*any* の計算問題を解き、*any* 形式の入力(例えば、漢字で書かれた負の数)を提供する。
正確性のために分析できる(プロブレム固有の)プログラムは存在しない。
また、 LLM が解を返すのに要する時間は、解決される問題の計算複雑性とは無関係である。
一般に、問題において、あるいはインスタンス固有の場合、経験的計算の能力や限界はどのようなものか?
我々の目的は、興味深い問題に満ちたSEのフィールドとして経験的計算を確立することである。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - On Hardware-efficient Inference in Probabilistic Circuits [5.335146727090435]
本研究は,PC用専用近似計算フレームワークを提案する。
我々はAddition As Intを活用し、単純なハードウェア要素による線形PC計算を実現した。
理論的近似誤差解析と誤り補償機構を提案する。
論文 参考訳（メタデータ） (2024-05-22T13:38:47Z) - 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) - Exceeding Computational Complexity Trial-and-Error Dynamic Action and
Intelligence [0.0]
計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。
本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。
また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
論文 参考訳（メタデータ） (2022-12-22T21:23:27Z) - Solving a Special Type of Optimal Transport Problem by a Modified
Hungarian Algorithm [2.1485350418225244]
本稿では,特殊な輸送問題 (OT) について検討し,それを正確に解くための改良されたハンガリーのアルゴリズムを提案する。
m$と$n$の原子を持つ辺り間のOT問題に対して、提案アルゴリズムの計算複雑性は$O(m2n)$である。
論文 参考訳（メタデータ） (2022-10-29T16:28:46Z) - Weighted Programming [0.0]
数学モデルを特定するためのプログラミングパラダイムである重み付けプログラミングについて研究する。
パラダイムとしての重み付きプログラミングは、確率分布を超えた数学的モデルを特定するのに利用できると論じる。
論文 参考訳（メタデータ） (2022-02-15T17:06:43Z) - On Theoretical Complexity and Boolean Satisfiability [0.0]
この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。
次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。
最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
論文 参考訳（メタデータ） (2021-12-22T10:13:34Z) - Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。
実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文 参考訳（メタデータ） (2021-09-14T20:52:55Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳（メタデータ） (2020-06-05T13:48:26Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。