Submodular set function (original) (raw)
Eine submodulare Funktion ist eine Mengenfunktion, die die Rangfunktion eines Matroids verallgemeinert. Submodulare Funktionen spielen in der kombinatorischen Optimierung eine wichtige Rolle.
| Property | Value |
|---|---|
| dbo:abstract | Eine submodulare Funktion ist eine Mengenfunktion, die die Rangfunktion eines Matroids verallgemeinert. Submodulare Funktionen spielen in der kombinatorischen Optimierung eine wichtige Rolle. (de) En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières. Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes. (fr) In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains. (en) 数学の分野において劣モジュラ関数 (英: submodular function) とは集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。 (ja) |
| dbo:wikiPageExternalLink | http://submodularity.org/ http://www.cs.berkeley.edu/~stefje/references.html |
| dbo:wikiPageID | 33273315 (xsd:integer) |
| dbo:wikiPageLength | 20470 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121394132 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Power_set dbr:Electrical_network dbr:Entropic_vector dbc:Matroid_theory dbr:Uniform_distribution_(continuous) dbc:Approximation_algorithms dbc:Combinatorial_optimization dbr:Maximum_cut dbr:Subadditive_set_function dbr:Elsevier dbr:Entropy_(information_theory) dbr:Game_theory dbr:Graph_(discrete_mathematics) dbr:Mutual_information dbr:NP-hard dbr:Concave_function dbr:Convex_function dbr:Approximation_algorithms dbr:László_Lovász dbr:Machine_learning dbr:Closure_(mathematics) dbr:Computer_vision dbr:Feature_selection dbr:Springer_Publishing dbr:Matroid dbr:Matroid_rank dbr:Maximum_coverage_problem dbr:Utility_functions_on_indivisible_goods dbr:Linear_combination dbr:Local_search_(optimization) dbr:Minimum_cut dbr:Active_learning_(machine_learning) dbr:Economics dbr:Oxford_University_Press dbr:Diminishing_returns dbr:Directed_graph dbr:Random_variable dbr:Restriction_(mathematics) dbr:Artificial_intelligence dbr:Automatic_summarization dbr:Greedy_algorithm dbr:Polynomial_time dbr:Budget-additive_valuation dbr:Optimization_problem dbr:Random_variables dbr:Set_(mathematics) dbr:Set_function dbr:Multi-document_summarization dbr:Polymatroid dbr:Supermodular_function |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Citation_needed dbt:Cleanup_bare_URLs dbt:Page_needed dbt:Reflist dbt:Short_description dbt:Use_American_English |
| dct:subject | dbc:Matroid_theory dbc:Approximation_algorithms dbc:Combinatorial_optimization |
| gold:hypernym | dbr:Function |
| rdf:type | yago:WikicatApproximationAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 |
| rdfs:comment | Eine submodulare Funktion ist eine Mengenfunktion, die die Rangfunktion eines Matroids verallgemeinert. Submodulare Funktionen spielen in der kombinatorischen Optimierung eine wichtige Rolle. (de) En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières. Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes. (fr) 数学の分野において劣モジュラ関数 (英: submodular function) とは集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。 (ja) In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, imag (en) |
| rdfs:label | Submodulare Funktion (de) Fonction sous-modulaire (fr) 劣モジュラ関数 (ja) Submodular set function (en) |
| owl:sameAs | freebase:Submodular set function yago-res:Submodular set function wikidata:Submodular set function dbpedia-de:Submodular set function dbpedia-fr:Submodular set function dbpedia-ja:Submodular set function https://global.dbpedia.org/id/4vr9w |
| prov:wasDerivedFrom | wikipedia-en:Submodular_set_function?oldid=1121394132&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Submodular_set_function |
| is dbo:wikiPageRedirects of | dbr:Submodular dbr:Submodular_function dbr:Submodular_maximization dbr:Submodular_valuation dbr:Submodular_valuations |
| is dbo:wikiPageWikiLink of | dbr:Pseudo-Boolean_function dbr:Strategic_complements dbr:Price_of_anarchy_in_auctions dbr:Deficiency_(graph_theory) dbr:Independence_Theory_in_Combinatorics dbr:Subadditive_set_function dbr:Alexander_Schrijver dbr:Egalitarian_item_allocation dbr:Correlation_gap dbr:Sigma-additive_set_function dbr:Combinatorics:_The_Rota_Way dbr:Feature_selection dbr:Fulkerson_Prize dbr:Matroid_rank dbr:Maximum_coverage_problem dbr:Utility_functions_on_indivisible_goods dbr:Additive_utility dbr:Bregman_divergence dbr:Diminishing_returns dbr:Fractionally-subadditive_valuation dbr:Cost-sharing_mechanism dbr:Bin_packing_problem dbr:Efficient_approximately-fair_item_allocation dbr:George_Nemhauser dbr:Automatic_summarization dbr:Gross_substitutes_(indivisible_items) dbr:Budget-additive_valuation dbr:Set_function dbr:Unit_demand dbr:Polymatroid dbr:Sequential_auction dbr:Structured_sparsity_regularization dbr:Supermodular_function dbr:Submodular dbr:Submodular_function dbr:Submodular_maximization dbr:Submodular_valuation dbr:Submodular_valuations |
| is foaf:primaryTopic of | wikipedia-en:Submodular_set_function |