論文の概要: Concave Aspects of Submodular Functions
- arxiv url: http://arxiv.org/abs/2006.16784v1
- Date: Sat, 27 Jun 2020 17:06:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 08:20:01.615691
- Title: Concave Aspects of Submodular Functions
- Title（参考訳）: 部分モジュラー関数の凹面
- Authors: Rishabh Iyer and Jeff Bilmes
- Abstract要約: 部分モジュラー関数はエントロピーや相互情報などの情報理論の量を一般化する。
部分モジュラ函数も凹凸の兆候を示す。
上界に付随する超微分と多面体を特徴付け, 微分を用いた部分モジュラーの最適条件を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Submodular Functions are a special class of set functions, which generalize
several information-theoretic quantities such as entropy and mutual information
[1]. Submodular functions have subgradients and subdifferentials [2] and admit
polynomial-time algorithms for minimization, both of which are fundamental
characteristics of convex functions. Submodular functions also show signs
similar to concavity. Submodular function maximization, though NP-hard, admits
constant-factor approximation guarantees, and concave functions composed with
modular functions are submodular. In this paper, we try to provide a more
complete picture of the relationship between submodularity with concavity. We
characterize the super-differentials and polyhedra associated with upper bounds
and provide optimality conditions for submodular maximization using the-super
differentials. This paper is a concise and shorter version of our longer
preprint [3].
- Abstract（参考訳）: 部分モジュラ函数は集合関数の特別なクラスであり、エントロピーや相互情報 [1] のような情報理論の量を一般化する。
部分モジュラ函数は次数と次数 [2] を持ち、最小化のための多項式時間アルゴリズムを許容するが、どちらも凸函数の基本的特性である。
部分モジュラ函数も凹凸と同様の符号を示す。
部分モジュラー関数の最大化はnpハードであるが、定数近似の保証を認め、モジュラー関数からなる凹関数は部分モジュラーである。
本稿では, 部分モジュラリティと凹凸の関係について, より完全な図式化を試みる。
上界に付随する超微分と多面体を特徴付け、超微分を用いた部分モジュラー最大化の最適条件を提供する。
この論文は、我々のより長いプレプリント [3] の簡潔で短いバージョンである。
関連論文リスト
- Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
格子上の函数の超モジュラー階数を定義する。
準モジュラーランクを類似的に定義する。
部分モジュラ分解を用いて集合関数を最適化する。
論文 参考訳（メタデータ） (2023-05-24T02:09:28Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。
本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
論文 参考訳（メタデータ） (2022-10-20T06:00:45Z) - Sparsification of Decomposable Submodular Functions [27.070004659301162]
サブモジュール関数は多くの機械学習とデータマイニングタスクの中核にある。
元の関数の根底にある部分モジュラ関数の数がとても多いので、処理に多くの時間が必要で、あるいはメインメモリに収まらない場合もあります。
分解可能部分モジュラ函数に対するスパーシフィケーションの概念を導入し、元の関数の正確な近似を得る目的は、少数の部分モジュラ函数の(重み付けされた)和である。
論文 参考訳（メタデータ） (2022-01-18T20:05:25Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Submodular Combinatorial Information Measures with Applications in
Machine Learning [2.5329739965085785]
エントロピーや相互情報のような情報理論の量は、機械学習で多くの用途を見出した。
本研究では,独立性,(条件)エントロピー,(条件)相互情報,および変数の集合上で定義された総相関を一般化する情報尺度について検討する。
論文 参考訳（メタデータ） (2020-06-27T17:45:32Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。
本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。
整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
論文 参考訳（メタデータ） (2020-06-01T22:20:45Z) - Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
我々は,群不変特徴ベクトルが線形分類器を学習する際に十分な識別情報を含んでいることを証明した。
主成分分析やk平均クラスタリングにおいて,グループアクションを明示的に考慮する新たな特徴モデルを提案する。
論文 参考訳（メタデータ） (2019-06-05T07:15:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。