論文の概要: Generative Models of Huge Objects
- arxiv url: http://arxiv.org/abs/2302.12823v1
- Date: Fri, 24 Feb 2023 18:58:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 12:34:31.751341
- Title: Generative Models of Huge Objects
- Title(参考訳): 巨大物体の生成モデル
- Authors: Lunjia Hu, Inbal Livni-Navon, Omer Reingold
- Abstract要約: 単一対象からの識別不可能性は、学習理論における生成モデルとグラフ理論における正規性補題の研究によって動機付けられる。
本研究では,いくつかの自然環境において,大きな識別不可能な物体に対する学習アルゴリズムを提案する。
結果は、学習理論、複雑性理論、暗号、ゲーム理論など、さまざまな分野の概念と技法に依存している。
- 参考スコア(独自算出の注目度): 6.7086472013021305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work initiates the systematic study of explicit distributions that are
indistinguishable from a single exponential-size combinatorial object. In this
we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that
focused on the implementation of huge objects that are indistinguishable from
the uniform distribution, satisfying some global properties (which they coined
truthfulness). Indistinguishability from a single object is motivated by the
study of generative models in learning theory and regularity lemmas in graph
theory. Problems that are well understood in the setting of pseudorandomness
present significant challenges and at times are impossible when considering
generative models of huge objects.
We demonstrate the versatility of this study by providing a learning
algorithm for huge indistinguishable objects in several natural settings
including: dense functions and graphs with a truthfulness requirement on the
number of ones in the function or edges in the graphs, and a version of the
weak regularity lemma for sparse graphs that satisfy some global properties.
These and other results generalize basic pseudorandom objects as well as
notions introduced in algorithmic fairness. The results rely on notions and
techniques from a variety of areas including learning theory, complexity
theory, cryptography, and game theory.
- Abstract(参考訳): この研究は、単一の指数サイズの組合せ対象と区別できない明示的な分布の体系的研究を開始する。
この中で、goldreich、goldwasser、nussboim(sicomp 2010)の仕事を拡張し、一様分布と区別できない巨大なオブジェクトの実装に焦点を当て、いくつかのグローバルな特性(真理性)を満たした。
単一対象との区別不能性は、学習理論における生成モデルとグラフ理論における正規性補題の研究によって動機付けられる。
擬似ランダム性の設定においてよく理解されている問題は重要な課題であり、巨大な物体の生成モデルを考えると時には不可能である。
本研究は,グラフ内の関数やエッジの個数に真理性を必要とする密関数とグラフ,いくつかの大域的性質を満足するスパースグラフに対する弱正規性補題のバージョンなど,いくつかの自然環境における巨大な識別不能な物体に対する学習アルゴリズムを提供することにより,その汎用性を示す。
これらの結果は、アルゴリズム的公正性に導入された概念と同様に、基本的な擬似ランダムオブジェクトを一般化する。
結果は、学習理論、複雑性理論、暗号、ゲーム理論など、さまざまな分野の概念と技法に依存している。
関連論文リスト
- Homomorphism Counts for Graph Neural Networks: All About That Basis [9.014929555228916]
グラフニューラルネットワークは、グラフ上の不変関数を学習するためのアーキテクチャである。
グラフ内の特定のパターンを数えることのできないことは、そのような制限の中心にある。
我々は、対象パターンの「基底」に全ての構造の準同型数を含むよりきめ細かいアプローチを論じる。
論文 参考訳(メタデータ) (2024-02-13T16:57:06Z) - Generative Learning of Continuous Data by Tensor Networks [47.77281294161002]
本稿では,連続データのためのテンソルネットワーク生成モデルについて紹介する。
我々は、このモデルの性能を、いくつかの合成および実世界のデータセットでベンチマークする。
本手法は, 急速に成長する生成学習分野において, 量子インスピレーション法の有効性を示す重要な理論的, 実証的な証拠を与える。
論文 参考訳(メタデータ) (2023-10-31T14:37:37Z) - Object-centric architectures enable efficient causal representation
learning [51.6196391784561]
観測対象が複数の物体である場合, 生成関数はもはや注入的ではなく, 実際に乱れは生じないことを示す。
スパース摂動からの弱い監督を利用して各オブジェクトのプロパティを乱すオブジェクト中心アーキテクチャを開発する。
このアプローチはユークリッド空間にエンコードする同等のアプローチよりもはるかに少ない摂動を必要とするという意味で、よりデータ効率が高い。
論文 参考訳(メタデータ) (2023-10-29T16:01:03Z) - What functions can Graph Neural Networks compute on random graphs? The
role of Positional Encoding [0.0]
我々は,グラフニューラルネットワーク(GNN)の大規模グラフに対する理論的理解を深めることを目指しており,その表現力に着目している。
近年、GNNは、非常に一般的なランダムグラフモデルにおいて、ノード数が増加するにつれて、特定の関数に収束することを示した。
論文 参考訳(メタデータ) (2023-05-24T07:09:53Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳(メタデータ) (2021-10-21T07:28:11Z) - Model-agnostic multi-objective approach for the evolutionary discovery
of mathematical models [55.41644538483948]
現代のデータ科学では、どの部分がより良い結果を得るために置き換えられるかというモデルの性質を理解することがより興味深い。
合成データ駆動型モデル学習において,多目的進化最適化を用いてアルゴリズムの所望特性を求める。
論文 参考訳(メタデータ) (2021-07-07T11:17:09Z) - Generalization and Robustness Implications in Object-Centric Learning [23.021791024676986]
本稿では,5つの共通オブジェクトデータセット上で,最先端の教師なしモデルを訓練する。
実験結果から,ダウンストリームタスクに一般的に有用なオブジェクト中心表現が得られた。
論文 参考訳(メタデータ) (2021-07-01T17:51:11Z) - Efficient Robustness Certificates for Discrete Data: Sparsity-Aware
Randomized Smoothing for Graphs, Images and More [85.52940587312256]
本稿では,初期作業を想定したランダム化平滑化フレームワークに基づくモデル非依存の証明書を提案する。
このアプローチがさまざまなモデル、データセット、タスクに対して有効であることを示します。
論文 参考訳(メタデータ) (2020-08-29T10:09:02Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。